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.

• Publication year

  2002

• Venue

  The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.

• Publication date

  2002-11-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.2002.1181985arXiv 1902.11169
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computable Analysis: An Introduction

  2014cited by this paper
• Data Structures and Algorithms 3

  2012cited by this paper
• On Resolution Complexity of Matching Principles

  2002cited by this paper
• Lower Bounds for Dynamic Data Structures on Algebraic RAMs

  2002cited by this paper
• Reporting Red—Blue Intersections between Two Sets of Connected Line Segments

  2002cited by this paper
• Structure and Hierarchy in Real-Time Systems

  2002cited by this paper
• Multiparty Computations Information-Theoretically Secure Against an Adaptive Adversary

  2002cited by this paper
• Robust and Flexible Scheduling with Evolutionary Computation

  2001cited by this paper
• On Static and Dynamic Control-Flow Information in Program Analysis and Transformation

  2001cited by this paper
• Algorithm Design: Foundations, Analysis, and Internet Examples

  2001cited by this paper
• Faster kinetic heaps and their use in broadcast scheduling

  2001influential reference
• Analyzing Real-Time Systems: Theory and Tools

  2001cited by this paper
• Topics in Semantics-based Program Manipulation

  2001cited by this paper
• Handbook of Computational Geometry

  2000cited by this paper
• Computational Geometry: Algorithms and Applications, Second Edition

  2000cited by this paper
• Logics and Automata for Verification: Expressiveness and Decidability Issues

  2000cited by this paper
• Dynamic Planar Convex Hull with Optimal Query Time

  2000influential reference
• Dynamic planar convex hull operations in near-logarithmic amortized time

  1999cited by this paper
• Remarks on k-Level Algorithms in the Plane

  1999influential reference
• Data structures for mobile data

  1997cited by this paper
• Sweeping lines and line segments with a heap

  1997cited by this paper
• Computational geometry: algorithms and applications, 3rd Edition

  1997cited by this paper
• Handbook of Discrete and Computational Geometry, Second Edition

  1997cited by this paper
• Complexity and Real Computation

  1997cited by this paper
• Computational geometry: algorithms and applications

  1997cited by this paper
• Optimal output-sensitive convex hull algorithms in two and three dimensions

  1996influential reference
• A BIBLIOGRAPHY OF

  1995cited by this paper
• Dynamic maintenance of 2-d convex hulls and order decomposable problems

  1995cited by this paper
• Constructing levels in arrangements and higher order Voronoi diagrams

  1994cited by this paper
• On geometric optimization with few violated constraints

  1994cited by this paper
• Dynamic algorithms in computational geometry

  1992cited by this paper
• Offline maintenance of planar configurations

  1991cited by this paper
• Applications of a semi-dynamic convex hull algorithm

  1990influential reference
• The cell probe complexity of dynamic data structures

  1989cited by this paper
• On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines

  1988cited by this paper
• The Design of Dynamic Data Structures

  1987influential reference
• The Ultimate Planar Convex Hull Algorithm?

  1986cited by this paper
• Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees

  1986cited by this paper
• Constructing Belts in Two-Dimensional Arrangements with Applications

  1986cited by this paper
• Amortized Computational Complexity

  1985cited by this paper
• An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

  1985cited by this paper
• Lower bounds for algebraic computation trees

  1983cited by this paper
• A new data structure for representing sorted lists

  1982cited by this paper
• Maintenance of Configurations in the Plane

  1981influential reference
• On the Omega(n log n) Lower Bound for Convex Hull and Maximal Vector Determination

  1980cited by this paper
• Decomposable Searching Problems I: Static-to-Dynamic Transformation

  1980cited by this paper
• Another Efficient Algorithm for Convex Hulls in Two Dimensions

  1979cited by this paper
• An optimal real-time algorithm for planar convex hulls

  1979influential reference
• Decomposable Searching Problems

  1979influential reference
• Convex hulls of finite sets of points in two and three dimensions

  1977cited by this paper
• On computing the length of longest increasing subsequences

  1975cited by this paper
• On the Identification of the Convex Hull of a Finite Set of Points in the Plane

  1973cited by this paper
• Organization and maintenance of large ordered indexes

  1972cited by this paper
• An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set

  1972cited by this paper

• Dynamic 3D Convex Hulls Revisited and Applications

  2026cites this paper
• Computing the center of uncertain points on cactus graphs

  2026cites this paper
• The Contiguous Art Gallery Problem is in Θ(n log n)

  2025cites this paper
• Practical Insertion-Only Convex Hull

  2025influential citation
• In search of the Giant Convex Quadrilateral hidden in the Mountains

  2025cites this paper
• Incremental Computing by Differential Execution (Artifact)

  2025cites this paper
• Fast Agnostic Learners in the Plane

  2025influential citation
• Online computation of normalized substring complexity

  2025cites this paper
• A Natural Way of Solving a Convex Hull Problem

  2025cites this paper
• The k-Center Problem of Uncertain Points on Graphs

  2025cites this paper
• Parallel Line Centers with Guaranteed Separation

  2025cites this paper
• Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice

  2025cites this paper
• Decremental Greedy Polygons and Polyhedra Without Sharp Angles

  2025cites this paper
• Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles

  2025cites this paper
• Combinatorial optimization of the coefficient of determination

  2024cites this paper
• Robust Classification of Dynamic Bichromatic point Sets in R2

  2024cites this paper
• Fast Area-Weighted Peeling of Convex Hulls for Outlier Detection

  2024influential citation
• Adaptive generative adjustable electric fence method and internal obstacle detection

  2024cites this paper
• Explainable decomposition of nested dense subgraphs

  2024cites this paper
• Dynamic Convex Hulls for Simple Paths

  2024influential citation
• Rectilinear convex hull of points in 3D and applications

  2024cites this paper
• Robust Bichromatic Classification using Two Lines

  2024cites this paper
• Constrained Two-Line Center Problems

  2024cites this paper
• Fully Dynamic Geometric Vertex Cover and Matching

  2024cites this paper
• An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism

  2023cites this paper
• Simple and Robust Dynamic Two-Dimensional Convex Hull

  2023influential citation
• How to compute the convex hull of a binary shape? A real-time algorithm to compute the convex hull of a binary shape

  2023cites this paper
• Dynamic Convex Hulls under Window-Sliding Updates

  2023influential citation
• Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors

  2022cites this paper
• DeepHull: Fast Convex Hull Approximation in High Dimensions

  2022cites this paper
• Computing the Minimum Bottleneck Moving Spanning Tree

  2022cites this paper
• Natural Way of Solving a Convex Hull Problem

  2022cites this paper
• Community detection in edge-labeled graphs

  2022cites this paper
• Using spatial data and cluster analysis to automatically detect non-trivial relationships between environmental transgressors

  2022cites this paper
• About the Reconstruction of Convex Lattice Sets from One or Two X-rays

  2022cites this paper
• Reconstruction of Convex Sets from One or Two X-rays

  2022cites this paper
• Dense subgraphs induced by edge labels

  2022cites this paper
• Dynamic Connectivity in Disk Graphs

  2021cites this paper
• Maintaining AUC and H-measure over time

  2021cites this paper
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

  2020cites this paper
• Rainbow polygons for colored point sets in the plane

  2020cites this paper
• Trajectory Visibility

  2020cites this paper
• Trajectory Planning for an Articulated Probe

  2020cites this paper
• Cutting Bamboo Down to Size

  2020cites this paper
• Building a Polyhedral Representation from an Instrumented Execution

  2019cites this paper
• Dynamic Geometric Data Structures via Shallow Cuttings

  2019cites this paper
• Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead

  2019cites this paper
• Incremental Approximate Computing

  2019cites this paper
• Two-center of the Convex Hull of a Point Set: Dynamic Model, and Restricted Streaming Model

  2019cites this paper
• Sweep Line Algorithm for Convex Hull Revisited

  2019cites this paper
• Dynamic Maintenance of the Lower Envelope of Pseudo-Lines

  2019cites this paper
• A Distributed Minimum Spanning Tree Based on all Best Swap Edges in CRN

  2019cites this paper
• Improved algorithms for dynamic lot sizing problems with incremental discount

  2019cites this paper
• Dynamic Maintenance of the Lower Envelope of Pseudo-Lines

  2019cites this paper
• An Optimal Algorithm to Compute the Inverse Beacon Attraction Region

  2018influential citation
• On the Complexity of the convex Hull problem under a RAM variant model

  2018cites this paper
• Collective Fast Delivery by Energy-Efficient Agents

  2018cites this paper
• Optimizing generalized kernels of polygons

  2018cites this paper
• Computing optimal shortcuts for networks

  2018cites this paper
• Streaming Algorithms for Planar Convex Hulls

  2018cites this paper
• 3D fast convex-hull-based evolutionary multiobjective optimization algorithm

  2018cites this paper
• Two-Stage Robust Unit Commitment for Co-Optimized Electricity Markets: An Adaptive Data-Driven Approach for Scenario-Based Uncertainty Sets

  2018cites this paper
• A Survey on Quantum Channel Capacities

  2018cites this paper
• An Efficient Kinetic Range Query for One Dimensional Axis Parallel Segments

  2018cites this paper
• DU Electronic Theses and Dissertations Graduate Studies 1-1-2011 Minimax and Maximin Fitting of Geometric Objects to Sets of Points

  2018cites this paper
• Improved Bounds on Absolute Positiveness of Multivariate Polynomials

  2017influential citation
• Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons

  2017cites this paper
• Finer-grained Locking in Concurrent Dynamic Planar Convex Hulls

  2017cites this paper
• A Convex Hull Algorithm using Point Elimination Technique

  2017cites this paper
• Improved Time-Space Trade-offs for Computing Voronoi Diagrams

  2017cites this paper
• 26 CONVEX HULL COMPUTATIONS

  2017cites this paper
• Finding a widest empty 1-corner corridor

  2017cites this paper
• Geometric Facility Location Problems on Uncertain Data

  2017cites this paper
• $K_{1, 3}$-covering red and blue points in the plane

  2017influential citation
• Efficient algorithms for beacon routing in polygons

  2017cites this paper
• An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

  2017cites this paper
• Covering Uncertain Points in a Tree

  2017cites this paper
• Efficient Delivery with Mobile Agents

  2017cites this paper
• Exact algorithms for size constrained 2-clustering in the plane

  2016cites this paper
• IncApprox: A Data Analytics System for Incremental Approximate Computing

  2016cites this paper
• Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace

  2016cites this paper
• Two Approaches to Building Time-Windowed Geometric Data Structures

  2016cites this paper
• Covering points with convex sets of minimum size

  2016cites this paper
• Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace

  2016cites this paper
• Degree four plane spanners: Simpler and better

  2016cites this paper
• 28 Arrangements

  2016cites this paper
• Outer common tangents and nesting of convex hulls of two disjoint simple polygons in linear time and constant workspace

  2016cites this paper
• 32nd International Symposium on Computational Geometry, SoCG 2016, Boston, MA, USA, June 14-18, 2016

  2016cites this paper
• The Marriage of Incremental and Approximate Computing

  2016cites this paper
• Disk Intersection Graphs: Models, Data Structures, and Algorithms

  2016cites this paper
• Thinnest V-shapes, Biggest Angles, and Lowest Potentials

  2016cites this paper
• An Optimal Algorithm for the Separating Common Tangents of two Polygons

  2015cites this paper
• Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks

  2015cites this paper
• 2 Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings 1 . 1 Standard Cuttings

  2015cites this paper
• Optimal straight-line labels for island groups

  2015cites this paper
• A novel Q-scanning for convex hull algorithm

  2015cites this paper
• Dynamic Connectivity for Unit Disk Graphs ∗

  2015cites this paper
• The use of geometric structures in graphics and optimization

  2015cites this paper
• Cartographic modelling for automated map generation

  2015cites this paper
• Near optimal line segment queries in simple polygons

  2015cites this paper