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

computational geometrydirected acyclic graphpoint locationrandomized incremental constructiontrapezoidal map

Mathematics Subject Classification ID

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

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.

Review text

The paper deals with one of the fundamental problems in computational geometry, namely with the planar point location. The authors revisit the randomized incremental construction of the trapezoidal map and the related search structures. At the beginning the authors describe the basic random incremental construction in which a trapezoidal map \(T\) is constructed and a directed acyclic graph \(G\) is maintained during the incremental construction. Moreover, some discussion on guaranteeing the logarithmic query time is made. Next, the authors study the depth \(D\) of \(G\) and the longest search path \(L\) in \(G\). They prove that the worst-case ratio between \(D\) and \(L\) can be \(\Theta(n / \log n)\), where \(n\) is the number of pairwise interior disjoint \(x\)-monotone curves inducing the planar subdivision. Later, they prove that there exists a bijection among all search paths in \(G\) and those in \(T\). Using these results the authors propose an algorithm for the construction of a trapezoidal map that has an expected \(O(n \log n)\) preprocessing time, an expected \(O(\log n)\) query time and requires an expected \(O(n)\) space.

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 fast planar partition algorithm. I
• A New Approach to Planar Point Location
• 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 randomized incremental construction for guaranteed logarithmic planar point location
• Optimal Search in Planar Subdivisions
• THE DELAUNAY HIERARCHY
• The design and implementation of panar maps in CGAL

Cited in

(4)

• 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?)
• A simple dynamization of trapezoidal point location in planar subdivisions

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)