Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection

DOI10.1016/j.comgeo.2010.04.005zbMath1254.65033MaRDI QIDQ991174

Timothy M. Chan, Eric Y. Chen

Publication date: 2 September 2010

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2010.04.005

zbMATH Keywords

Voronoi diagrams; convex hulls; cache-oblivious algorithms; in-place algorithms; segment intersection

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Related Items

Reprint of: Memory-constrained algorithms for simple polygons, In-place algorithms for computing a largest clique in geometric intersection graphs, Memory-constrained algorithms for simple polygons

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• Space-efficient planar convex hull algorithms
• Implicit \(B\)-trees: A new data structure for the dictionary problem
• In-place algorithms for computing (Layers of) maxima
• Space-efficient geometric divide-and-conquer algorithms
• Derandomizing an output-sensitive convex hull algorithm in three dimensions
• Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• Line-segment intersection made in-place
• Optimal implicit dictionaries over unbounded universes
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
• Cache-Oblivious Algorithms
• Succinct geometric indexes supporting point location queries
• Radix Sorting with No Extra Space
• Cache-Oblivious Red-Blue Line Segment Intersection
• An in-place sorting with O ( n log n ) comparisons and O ( n ) moves
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
• Optimal Point Location in a Monotone Subdivision
• A New Approach to Planar Point Location
• Optimal Search in Planar Subdivisions
• Multidimensional Searching Problems
• Convex hulls of finite sets of points in two and three dimensions
• An optimal algorithm for intersecting line segments in the plane
• On the Exact Worst Case Query Complexity of Planar Point Location
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Algorithm Theory - SWAT 2004
• Incremental constructions con BRIO
• Towards in-place geometric algorithms and data structures
• In-Place Suffix Sorting
• Algorithms – ESA 2005