Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time

DOI10.1137/07068669XzbMath1200.68122OpenAlexW2168320878WikidataQ60638766 ScholiaQ60638766MaRDI QIDQ3558019

Mihai Pǎtraşcu, Timothy M. Chan

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

zbMATH Keywords

sortingdata structurescomputational geometrysearchingVoronoi diagramsconvex hullssegment intersectionword-RAM algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (8)

Adaptive Point Location in Planar Convex Subdivisions ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ Random access in persistent strings and segment selection ⋮ A faster algorithm for computing motorcycle graphs ⋮ Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection ⋮ Optimal deterministic algorithms for 2-d and 3-d shallow cuttings ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ On constant factors in comparison-based geometric algorithms and data structures

This page was built for publication: Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time