Relative Convex Hulls in Semi-Dynamic Arrangements
We present a data structure for maintaining the geodesic hull of a set of points (sites) in the presence of pairwise noncrossing line segments (barriers) that subdivide a bounding box into simply connected faces. For m barriers and n sites, our data structure has O((m+n)logn) size. It supports a mixed sequence of O(m) barrier insertions and O(n) site deletions in \(O((m+n) \operatorname{polylog}(mn))\) total time, and answers analogues of standard convex hull queries in \(O(\operatorname{polylog}(mn))\) time.
relative convex hull semi-dynamic data structure plane sweep