Efficiently updating constrained Delaunay triangulations (Q688628)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Efficiently updating constrained Delaunay triangulations
scientific article

    Statements

    Efficiently updating constrained Delaunay triangulations (English)
    0 references
    0 references
    0 references
    30 November 1993
    0 references
    The Constrained 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 edges set of the triangulation contains all these obstacles. In this paper we present an optimal \(\Theta(\log n + k)\) algorithm for inserting an obstacle line segment or deleting an obstacle edge in the constrained Delaunay triangulation of a set of \(n\) obstacle line segments in the plane. Here \(k\) is the number of Delaunay edges deleted and added in the triangulation during the updates.
    0 references
    constrained Delaunay triangulation
    0 references

    Identifiers