Incremental and Decremental Maintenance of Planar Width |
| |
Authors: | David Eppstein |
| |
Institution: | Department of Information and Computer Science, University of California, Irvine, California, 92697-3425, f1 |
| |
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ε) 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 ε > 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(nε). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|