Off-Line Maintenance of Planar Configurations |
| |
Authors: | John Hershberger Subhash Suri |
| |
Institution: | aMentor Graphics, 1001 Ridder Park Drive, San Jose, California, 95131;bDepartment of Computer Science, Washington University, St. Louis, Missouri, 63130 |
| |
Abstract: | We achieve anO(log n) amortized time bound per operation for the off-line version of the dynamic convex hull problem in the plane. In this problem, a sequence ofninsert,delete, andqueryinstructions are to be processed, where each insert instruction adds a new point to the set, each delete instruction removes an existing point, and each query requests a standard convex hull search. We process the entire sequence in totalO(n log n) time andO(n) space. Alternatively, we can preprocess a sequence ofninsertions and deletions inO(n log n) time and space, then answer queries in history inO(log n) time apiece (a query in history means a query comes with a time parametert, and it must be answered with respect to the convex hull present at timet). The same bounds also hold for the off-line maintenance of several related structures, such as the maximal vectors, the intersection of half-planes, and the kernel of a polygon. Achieving anO(log n) per-operation time bound for theon-lineversions of these problems is a longstanding open problem in computational geometry. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|