Incremental and Decremental Maintenance of Planar Width
<|reference_start|>Incremental and Decremental Maintenance of Planar Width: 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).<|reference_end|>
@article{eppstein1998incremental,
    title={Incremental and Decremental Maintenance of Planar Width},
    author={David Eppstein},
    journal={J. Algorithms 37(2):570-577, Nov. 2000},
    year={1998},
    doi={10.1006/jagm.2000.1107},
    archivePrefix={arXiv},
    eprint={cs/9809038},
    primaryClass={cs.CG}
}