Saumi Bandyopadhyay
"Three Problems About Dynamic Convex Hulls" by Timothy Chan
We present three results related to dynamic convex hulls:
-
A fully dynamic data structure for maintaining a set of n points in the plane so that we
can and the edges of the convex hull intersecting a query line, with expected query and
amortized update time O(log1+" n) for an arbitrarily small constant " > 0. This improves
the previous bound of O(log3=2 n).
-
A fully dynamic data structure for maintaining a set of n points in the plane to support
halfplane range reporting queries in O(logn+k) time with O(polylogn) expected amortized
update time. A similar result holds for 3-dimensional orthogonal range reporting. For
3-dimensional halfspace range reporting, the query time increases to O(log2 n= log logn+k).
-
A semi-online dynamic data structure for maintaining a set of n line segments in the plane,
so that we can decide whether a query line segment lies completely above the lower envelope,
with query time O(logn) and amortized update time O(n"). As a corollary, we can solve
the following problem in O(n1+") time: given a triangulated terrain in 3-d of size n, identify
all faces that are partially visible from a fixed viewpoint.