We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
THREE PROBLEMS ABOUT DYNAMIC CONVEX HULLS.
- Authors
CHAN, TIMOTHY M.
- Abstract
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 find 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/2n). A fully dynamic data structure for maintaining a set of n points in the plane to support halfplane range reporting queries in O(log n + 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(log² n/ log log n + 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.
- Subjects
CONVEX domains; DYNAMIC data exchange; ORTHOGONAL systems; DATA structures; LINEAR programming; MATHEMATICAL decomposition; LOGARITHMS
- Publication
International Journal of Computational Geometry & Applications, 2012, Vol 22, Issue 4, p341
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195912600096