Dynamic Planar Convex Hull

In this paper we determine the computational complexity of the dynamic convex hull problem in the planar case. We present a data structure that maintains a finite set of n points in the plane under insertion and deletion of points in amortized O(log n) time per operation. The space usage of the data structure is O(n). The data structure supports extreme point queries in a given direction, tangent queries through a given point, and queries for the neighboring points on the convex hull in O(log n) time. The extreme point queries can be used to decide whether or not a given line intersects the convex hull, and the tangent queries to determine whether a given point is inside the convex hull. We give a lower bound on the amortized asymptotic time complexity that matches the performance of this data structure.

Authors

• Gerth Stølting Brodal
• Riko Jacob

Keywords

• Data structures
• Computer science
• Computational geometry
• Tree data structures
• Contracts
• Jacobian matrices
• Computational complexity
• Fingers
• Application software
• Clocks
• Convex Hull
• Data Structure
• Space Usage
• Points In Plane
• Finite Set Of Points
• Lower Bound
• Secondary Structure
• Running Time
• Vertical Line
• Selection Of Points
• Tree Search
• Details Of Construction
• Update Time
• Variant Of Problem
• Split Point
• Query Time
• Operator Splitting
• Worst-case Time
• Merge Operation
• Balanced Tree
• Lower Envelope
• Segment Endpoints
• Chunk Size
• Fast Query
• Update Operation