2003 | OriginalPaper | Chapter
Adapting (Pseudo)-Triangulations with a Near-Linear Number of Edge Flips
Authors : Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser
Published in: Algorithms and Data Structures
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In geometric data processing, structures that partition the geometric input, as well as connectivity structures for geometric objects, play an important role. A versatile tool in this context are triangular meshes, often called triangulations; see e.g., the survey articles [6, 12, 5]. A triangulation of a finite set S of points in the plane is a maximal planar straight-line graph that uses all and only the points in S as its vertices. Each face in a triangulation is a triangle spanned by S. In the last few years, a relaxation of triangulations, called pseudo-triangulations (or geodesic triangulations), has received considerable attention. Here, faces bounded by three concave chains, rather than by three line segments, are allowed. The scope of applications of pseudo-triangulations as a geometric data stucture ranges from ray shooting [10, 14] and visibility [25, 26] to kinetic collision detection [1, 21, 22], rigidity [32, 29, 15], and guarding [31]. Still, only very recently, results on the combinatorial properties of pseudo-triangulations have been obtained. These include bounds on the minimal vertex and face degree [20] and on the number of possible pseudo-triangulations [27, 3]. The usefulness of (pseudo-)triangulations partially stems from the fact that these structures can be modified by constant-size combinatorial changes, commonly called flip operations. Flip operations allow for an adaption to local requirements, or even for generating globally optimal structures [6, 12]. A classical result states that any two triangulations of a given planar point set can be made to coincide by applying a quadratic number of edge flips; see e.g. [16, 19]. A similar result has been proved recently for the class of minimum pseudo-triangulations [8, 29].