Incremental and Decremental Maintenance of Planar Width

DOI10.1006/JAGM.2000.1107MaRDI QIDQ4521530zbMATH OpenOpenAlexFDO

Authors David Eppstein

Publication date 19 December 2000

Published in Journal of Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

width of a planar point set

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(kn^epsilon) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and epsilon is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(n^epsilon).

Recommendations

• scientific article; zbMATH DE number 1305508
• The effect of planarization on width
• The effect of planarization on width
• Off-line dynamic maintenance of the width of a planar point set
• A fully dynamic algorithm for planar width
• A fully dynamic algorithm for planar
• Off-Line Maintenance of Planar Configurations
• Construction of the planar bodies with constant width
• Planar width of regular maps

Cited in

(6)

• Off-line dynamic maintenance of the width of a planar point set
• A fully dynamic algorithm for planar width
• Two approaches to building time-windowed geometric data structures
• scientific article; zbMATH DE number 1629856 (Why is no real title available?)
• scientific article; zbMATH DE number 1305508 (Why is no real title available?)
• Constrained two-line center problems

This page was built for publication: Incremental and Decremental Maintenance of Planar Width

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