Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
DOI10.1016/J.COMGEO.2010.04.005zbMATH Open1254.65033OpenAlexW2044633855MaRDI QIDQ991174FDOQ991174
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
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Cites Work
- 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
- Cache-oblivious algorithms
- Title not available (Why is that?)
- Optimal Search in Planar Subdivisions
- An optimal algorithm for intersecting line segments in the plane
- Optimal Point Location in a Monotone Subdivision
- A New Approach to Planar Point Location
- Multidimensional Searching Problems
- On the Exact Worst Case Query Complexity of Planar Point Location
- Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
- Towards in-place geometric algorithms and data structures
- Space-efficient planar convex hull algorithms
- An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
- Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams
- Convex hulls of finite sets of points in two and three dimensions
- In-place algorithms for computing (Layers of) maxima
- Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
- Space-efficient geometric divide-and-conquer algorithms
- In-Place Suffix Sorting
- Succinct geometric indexes supporting point location queries
- Implicit \(B\)-trees: A new data structure for the dictionary problem
- Optimal implicit dictionaries over unbounded universes
- Title not available (Why is that?)
- Derandomizing an output-sensitive convex hull algorithm in three dimensions
- Incremental constructions con BRIO
- Radix Sorting with No Extra Space
- Algorithm Theory - SWAT 2004
- Title not available (Why is that?)
- Line-segment intersection made in-place
- Title not available (Why is that?)
- RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
- An in-place sorting with O ( n log n ) comparisons and O ( n ) moves
- Cache-Oblivious Red-Blue Line Segment Intersection
- Algorithms – ESA 2005
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
- Title not available (Why is that?)
- 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)
