5
$\begingroup$

If there's no deletion, we can use $2$ balanced trees to maintain $2$ half convex hulls(up and down). In this way, we can insert $n$ points in $O(n\log n)$ time.(In the beginning, there are no points)

A completely dynamic convex hull means that I can insert and delete a point without rebuilding the whole convex hull, which costs $O(n)$'s time.

My problem is, is there any solutions to deleting points quickly? Maybe it could be solved with persistent data structures, but up to now, I haven't come up with any concrete method yet.

$\endgroup$
1
$\begingroup$

This was first solved by Jacob and Brodal in 2002; there is a recent arXiv submission of that work, "Dynamic Planar Convex Hull".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.