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

DOI10.1016/J.COMGEO.2010.04.005MaRDI QIDQ991174zbMATH OpenOpenAlexFDO

Authors 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

convex hullsVoronoi diagramscache-oblivious algorithmsin-place algorithmssegment intersection

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection
• Instance-optimal geometric algorithms
• Line-segment intersection made in-place
• Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
• Optimal time-space tradeoff for the 2D convex-hull problem

Cites work

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

Cited in

(9)

• Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection
• Memory-constrained algorithms for simple polygons
• Optimal time-space tradeoff for the 2D convex-hull problem
• The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs
• In-place algorithms for computing a largest clique in geometric intersection graphs
• Instance-optimal geometric algorithms
• Intersections and circuits in sets of line segments
• scientific article; zbMATH DE number 2086251 (Why is no real title available?)
• Reprint of: Memory-constrained algorithms for simple polygons

This page was built for publication: Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991174)