A simple dynamization of trapezoidal point location in planar subdivisions

DOI10.4230/LIPICS.ICALP.2020.18MaRDI QIDQ6842560zbMATH OpenFDO

Authors Milutin Brankovic, Nikola Grujic, André van Renssen, Martin P. Seybold

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.18

zbMATH Keywords

backward analysisdynamizationorder-maintenanceplanar subdivisionpoint locationtrapezoidal search dagtrapezoidal search treetreap

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A fast planar partition algorithm. I
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Computational geometry. Algorithms and applications.
• Dynamic Planar Point Location in External Memory.
• Dynamic Point Location in General Subdivisions
• Dynamic Trees and Dynamic Point Location
• DYNAMIZATION OF THE TRAPEZOID METHOD FOR PLANAR POINT LOCATION IN MONOTONE SUBDIVISIONS
• File maintenance: when in doubt, change the layout!
• scientific article; zbMATH DE number 1303547 (Why is no real title available?)
• Lower bounds for kinetic planar subdivisions
• Maintaining order in a generalized linked list
• New Results on Dynamic Planar Point Location
• Optimal randomized incremental construction for guaranteed logarithmic planar point location
• Point location in dynamic planar subdivisions
• Randomized search trees
• Rational points on the unit sphere. Approximation complexity and practical constructions
• Towards an optimal method for dynamic planar point location

Cited in

(1)

• B-treaps revised: write efficient randomized block search trees with high load

This page was built for publication: A simple dynamization of trapezoidal point location in planar subdivisions

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