Efficiently updating constrained Delaunay triangulations |
| |
Authors: | Cao An Wang |
| |
Institution: | (1) Department of Computer Science, Memorial University of Newfoundland, A1C 5S7 St. John's, Newfoundland, Canada |
| |
Abstract: | TheConstrained Delaunay Triangulation of a set of obstacle line segments in the plane is the Delaunay triangulation of the endpoint set of these obstacles with the restriction that the edge set of the triangulation contains all these obstacles. In this paper we present an optimal (logn +k) algorithm for inserting an obstacle line segment or deleting an obstacle edge in the constrained Delaunay triangulation of a set ofn obstacle line segments in the plane. Herek is the number of Delaunay edges deleted and added in the triangulation during the updates.This work is supported by NSERC grant OPG0041629. |
| |
Keywords: | F 2 1 |
本文献已被 SpringerLink 等数据库收录! |
|