Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
DOI10.1137/07068669XzbMATH Open1200.68122OpenAlexW2168320878WikidataQ60638766 ScholiaQ60638766MaRDI QIDQ3558019FDOQ3558019
Authors: Timothy M. Chan, Mihai Patrascu 
Publication date: 29 April 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/07068669x
Recommendations
- Dynamic planar orthogonal point location in sublogarithmic time
- A time-space trade-off for triangulations of points in the plane
- Efficient computation of the geodesic Voronoi diagram of points in a simple polygon
- On a class of \(O(n^2)\) problems in computational geometry
- On a class of \(O(n^ 2)\) problems in computational geometry
- On geodesic properties of polygons relevant to linear time triangulation
- Sublinear geometric algorithms
- Sublinear Geometric Algorithms
- A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
- A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
computational geometrydata structuresconvex hullssortingVoronoi diagramssearchingsegment intersectionword-RAM algorithms
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cited In (13)
- Title not available (Why is that?)
- Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
- Polynomial data structure lower bounds in the group model
- On constant factors in comparison-based geometric algorithms and data structures
- Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
- On constant factors in comparison-based geometric algorithms and data structures
- Succinct and Implicit Data Structures for Computational Geometry
- A faster algorithm for computing motorcycle graphs
- Optimal randomized incremental construction for guaranteed logarithmic planar point location
- Adaptive Point Location in Planar Convex Subdivisions
- Succinct geometric indexes supporting point location queries
- Random access in persistent strings and segment selection
- Sublinear Geometric Algorithms
This page was built for publication: Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3558019)
