Incremental and Decremental Maintenance of Planar Width

Details Incremental and Decremental Maintenance of Planar Width Incremental and Decremental Maintenance of Planar Width

1998-09-21

arxiv.org/abs/cs/9809038v2

J. Algorithms 37(2):570-577, Nov. 2000

Computer Science

Computational Geometry

7 pages; 2 figures. A preliminary version of this paper was presented at the 10th ACM/SIAM Symp. Discrete Algorithms (SODA '99

Scientific paper

10.1006/jagm.2000.1107

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).

Affiliated with

Also associated with

No associations

Rating

Incremental and Decremental Maintenance of Planar Width does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Incremental and Decremental Maintenance of Planar Width, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incremental and Decremental Maintenance of Planar Width will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-360704