Optimal randomized incremental construction for guaranteed logarithmic planar point location

DOI10.1016/j.comgeo.2016.07.006zbMath1357.65023arXiv1410.5602OpenAlexW1836974482MaRDI QIDQ340542

Dan Halperin, Michael Hemmer, Michal Kleinbort

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)

Related Items (1)

Optimal randomized incremental construction for guaranteed logarithmic planar point location

Uses Software

• CGAL

Cites Work

• Optimal randomized incremental construction for guaranteed logarithmic planar point location
• CGAL Arrangements and their applications. A step-by-step guide
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• A fast planar partition algorithm. I
• Improved Implementation of Point Location in General Two-Dimensional Subdivisions
• THE DELAUNAY HIERARCHY
• Optimal Point Location in a Monotone Subdivision
• A New Approach to Planar Point Location
• Optimal Search in Planar Subdivisions
• Multidimensional Searching Problems
• Location of a Point in a Planar Subdivision and Its Applications
• Constructing Planar Cuttings in Theory and Practice
• On the Exact Worst Case Query Complexity of Planar Point Location
• The design and implementation of panar maps in CGAL
• Unnamed Item
• Unnamed Item
• Unnamed Item

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