Optimal randomized incremental construction for guaranteed logarithmic planar point location

DOI10.1016/J.COMGEO.2016.07.006MaRDI QIDQ340542zbMATH OpenOpenAlexFDO

Authors Michael Hemmer, Michal Kleinbort, Dan Halperin

Publication date 14 November 2016

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.5602

zbMATH Keywords

directed acyclic graphcomputational geometrypoint locationrandomized incremental constructiontrapezoidal map

Mathematics Subject Classification ID

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

Abstract: Given a planar map of $n$ segments in which we wish to efficiently locate points, we present the first randomized incremental construction of the well-known trapezoidal-map search-structure that only requires expected $O(nlogn)$ preprocessing time while deterministically guaranteeing worst-case linear storage space and worst-case logarithmic query time. This settles a long standing open problem; the best previously known construction time of such a structure, which is based on a directed acyclic graph, so-called the history DAG, and with the above worst-case space and query-time guarantees, was expected $O(nlo{g}^{2}n)$. The result is based on a deeper understanding of the structure of the history DAG, its depth in relation to the length of its longest search path, as well as its correspondence to the trapezoidal search tree. Our results immediately extend to planar maps induced by finite collections of pairwise interior disjoint well-behaved curves.

Recommendations

• scientific article; zbMATH DE number 1617272
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
• Towards an optimal method for dynamic planar point location
• Adaptive Point Location in Planar Convex Subdivisions
• A simple entropy-based algorithm for planar point location

Cites work

• A New Approach to Planar Point Location
• A fast planar partition algorithm. I
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• A simple entropy-based algorithm for planar point location
• CGAL Arrangements and their applications. A step-by-step guide
• Computational geometry. Algorithms and applications.
• Constructing Planar Cuttings in Theory and Practice
• Entropy-preserving cuttings and space-efficient planar point location
• Improved implementation of point location in general two-dimensional subdivisions
• Location of a Point in a Planar Subdivision and Its Applications
• Multidimensional Searching Problems
• On the Exact Worst Case Query Complexity of Planar Point Location
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions
• Optimal randomized incremental construction for guaranteed logarithmic planar point location
• THE DELAUNAY HIERARCHY
• The design and implementation of panar maps in CGAL

Cited in

(3)

• Lower bounds for expected-case planar point location
• Optimal randomized incremental construction for guaranteed logarithmic planar point location
• scientific article; zbMATH DE number 1779434 (Why is no real title available?)

Describes a project that uses

Uses Software

• CGAL

This page was built for publication: Optimal randomized incremental construction for guaranteed logarithmic planar point location

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q340542)