Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
From MaRDI portal
Publication:991174
DOI10.1016/j.comgeo.2010.04.005zbMath1254.65033OpenAlexW2044633855MaRDI QIDQ991174
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Related Items (5)
Memory-constrained algorithms for simple polygons ⋮ Reprint of: Memory-constrained algorithms for simple polygons ⋮ 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 ⋮ Intersections and circuits in sets of line segments
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
This page was built for publication: Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
