Dynamic convex hulls for simple paths

DOI10.4230/LIPICS.SOCG.2024.24MaRDI QIDQ6895881zbMATH OpenFDO

Authors Bruce Brewer, Gerth Stølting Brodal, Haitao Wang

Publication date 24 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.24

zbMATH Keywords

convex hull queriesdequedynamic convex hullpath updatessimple paths

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• Algorithms for subpath convex hull queries and ray-shooting among segments
• An efficient algorithm for determining the convex hull of a finite planar set
• An efficient algorithm for finding the CSG representation of a simple polygon
• An optimal real-time algorithm for planar convex hulls
• Another efficient algorithm for convex hulls in two dimensions
• Applications of a semi-dynamic convex hull algorithm
• AVL-trees for localized search
• Cartographic line simplification and polygon CSG formulae in O(n^* n) time
• COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS
• Dynamic convex hulls under window-sliding updates
• Dynamic planar convex hull operations in near-logarithmic amortized time
• Efficiently Planning Compliant Motion in the Plane
• Faster kinetic heaps and their use in broadcast scheduling. (Extended abstract)
• Finding the convex hull of a simple polygon
• Fractional cascading. II: Applications
• scientific article; zbMATH DE number 1617248 (Why is no real title available?)
• scientific article; zbMATH DE number 432803 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1263185 (Why is no real title available?)
• Maintenance of configurations in the plane
• Making data structures persistent
• On-line construction of the convex hull of a simple polyline
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• The design of dynamic data structures
• The Ultimate Planar Convex Hull Algorithm?
• Worst-case data structures for the priority queue with attrition

Cited in

(1)

• Dynamic convex hulls for simple paths

This page was built for publication: Dynamic convex hulls for simple paths

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