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

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

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
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
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
Derandomizing an output-sensitive convex hull algorithm in three dimensions
Incremental constructions con BRIO
Radix Sorting with No Extra Space
Algorithm Theory - SWAT 2004
Line-segment intersection made in-place
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 (5)

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
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)