Computing Pseudotriangulations via Branched Coverings

Abstract

We describe an efficient algorithm to compute a pseudotriangulation of a finite planar family of pairwise disjoint convex bodies presented by its chirotope. The design of the algorithm relies on a deepening of the theory of visibility complexes and on the extension of that theory to the setting of branched coverings. The problem of computing a pseudotriangulation that contains a given set of bitangent line segments is also examined.

1 Introduction

1.1 Main Result of the Paper

Throughout the paper we address the problem of computing efficiently a pseudotriangulation of a finite planar family of pairwise disjoint convex bodies presented by its chirotope: Here the term chirotope refers to a natural extension to finite planar families of pairwise disjoint convex bodies of the classical notion of chirotope (or order type) of a finite planar family of points [6, 7]; and the term planar refers to any oriented topological plane on ℝ², e.g., Euclidean plane, hyperbolic plane, Moulton planes, arc planes, etc.; cf. Appendix A.

1.1.1 Chirotopes

Recall that the chirotope of a finite planar family of points is (or can be defined as) the map that assigns to each ordered triple of distinct indices of the family of points the position vector of the corresponding ordered triple of points, that is, the boolean vector of truth-values of the five relations “the third point of the triple belongs to the open left side (open right side, initial part, median part, final part) of the directed line joining the first point of the triple to the second point of the triple.” Figure 1 shows five families of three points realizing the five possible chirotopes on the indexing set {1,2,3}. In this figure the plane is represented by the interior of a circular diagram, marked with a little oriented circle to indicate its orientation, and each diagram is labeled at its left bottom corner with a symbol to name it and at its right bottom corner with the position vector of the ordered triple of points corresponding to the ordered triple of indices 1,2,3. The notion of chirotope of a planar family of pairwise disjoint convex bodies is defined similarly: as for families of points we use the notion of position vector as a coding of the relative positions of the convex bodies with respect to a line. To set out the definition we use the following standard terminology: a directed bitangent joining an ordered pair of disjoint convex bodies is, as illustrated in the left part of Fig. 2, classified left–left, right–right, left–right or right–left depending on which sides (left or right side) of the bitangent are the convex bodies; walking along a directed bitangent we traverse successively, as illustrated in the middle part of Fig. 2, its initial, median and final parts; the median part of a bitangent is called a bitangent line segment thereafter. Using this terminology we are able to define the chirotope of a finite planar family of pairwise disjoint convex bodies as the map that assigns to each ordered triple of distinct indices of the family of bodies the position vector of the corresponding ordered triple of bodies, that is, the boolean vector of truth-values of the 20 relations “the third body of the triple intersects the open left side (open right side, initial part, median part, final part) of the left–left (left–right, right–left, right–right) directed bitangent joining the first body of the triple to the second body of the triple.” For example, consider the family of three convex bodies on the indexing set {1,2,3} depicted together with its 3×4 bitangents in the right part of Fig. 2 (six of the 12 bitangents are tritangents). Then its chirotope is the map χ defined by

$$\begin{array}{ll@{\ \ \ }l@{\ \ \ }l@{\ \ \ }l} & {\text{right--left}} &\text{right--right} &{\text{left--left}} &\text {left--right} \\ \chi(1,3,2) = \chi(3,1,2) = & 11010 & 01010 & 10010 & 11010\phantom{.} \\ \chi(1,2,3) = \chi(3,2,1) = & 10000 & 01001 & 10001 & 01000\phantom{.} \\ \chi(2,3,1) = \chi(2,1,3) = & 01000 & 01100 & 10100 & 10000. \end{array} $$

The number of chirotopes of planar families of three pairwise disjoint convex bodies on a given indexing set of size 3 is 531 and among these 531 chirotopes 118 are simple chirotopes, that is, chirotopes of families of convex bodies with no tritangent; as for the chirotope of a planar family of points a key feature of the chirotope of a planar family of pairwise disjoint convex bodies is that it encodes its dual arrangement, i.e., the arrangement, in the space of lines of the plane, of the curves of tangents to the bodies; cf. Appendix A. Throughout the paper we will assume that the boundaries of the bodies are free of line segments and that there is exactly one tangent through each boundary point; these assumptions facilitate the geometric definition of pseudotriangulations without ruling out any chirotope of families of pairwise disjoint convex bodies.

Fig. 1

Five families of three points realizing the five possible chirotopes on the indexing set {1,2,3}

Fig. 2

(Left) The left–left, left–right, right–left and right–right directed bitangents joining an ordered pair of disjoint convex bodies; (Middle) The left and right sides of a directed bitangent and its initial, median and final parts; (Right) A family of three pairwise disjoint convex bodies with its 3×4 bitangents of which 6 are tritangents

1.1.2 Pseudotriangulations

Let o ₁,o ₂,…,o _n be a finite planar family of n pairwise disjoint convex bodies; a boundary bitangent line segment is a bitangent line segment of the o _i contained in the boundary of their convex hull; all other bitangent line segments are said to be interior bitangent line segments; the number of boundary bitangent line segments is denoted h; free space is the complement in the plane of the interiors of the o _i ; a pseudotriangulation is a maximal (for the inclusion relation) family of pairwise interior non-crossing free bitangent line segments. A pseudotriangulation contains the h boundary bitangent line segments plus 3n−3−h interior bitangent line segments (thus 3n−3 altogether) and induces a decomposition of the free part of the convex hull of the o _i into 2n−2 pseudotriangles [37]. Figure 3 shows a family of 7 pairwise disjoint convex bodies of the real affine plane, its (six in number) boundary bitangent line segments, and one of its pseudotriangulation. The set of pseudotriangulations of a family of convex bodies depends only on its chirotope; cf. Appendix B. Therefore it is sensible to ask if a pseudotriangulation of a family of convex bodies presented by its chirotope is efficiently computable and, more generally, it is sensible to ask if a pseudotriangulation that contains a given set of pairwise interior non-crossing distinguished free bitangent line segments is efficiently computable. The main result of the paper is a positive answer to the first question and, at the same price, a positive answer to a restricted version of the second question.

Fig. 3

A family of seven pairwise disjoint convex bodies of the real affine plane, its boundary bitangent line segments, and one of its pseudotriangulations

Theorem 1.1

A pseudotriangulation (and in particular the boundary bitangent line segments) of a finite planar family of n pairwise disjoint convex bodies presented by its chirotope is computable in O(nlogn) time and linear space. A similar result holds for the problem of computing a pseudotriangulation that contains a given set of pairwise interior non-crossing distinguished free bitangent line segments, under the assumption that the number of distinguished bitangent line segments that appear consecutively on the boundary of any pseudotriangle of any pseudotriangulation of the family of convex bodies containing the distinguished bitangent line segments is a constant.

1.1.3 Three Independent Algorithms

Subsequently we use the term family of pairwise disjoint convex bodies with constraints for a finite planar family of pairwise disjoint convex bodies together with a, possibly empty, set of pairwise interior non-crossing distinguished free bitangent line segments, the constraints for short; in this context, free space is the space obtained by cutting the complement in the plane of the interiors of the convex bodies along the constraints: this is the disjoint union of two-dimensional surfaces whose cuffs contain exactly one cusp point per endpoint of constraint (counting multiplicities); in particular if the set of constraints is a pseudotriangulation, free space is the disjoint union of the pseudotriangles of the pseudotriangulation plus the complement in the plane of the interior of the convex hull of the bodies. The family will be said well-constrained if it satisfies the condition stated in the theorem above, that is, if the number of constraints that appear consecutively on the boundary of any pseudotriangle of any completion of the set of constraints into a pseudotriangulation of the family of convex bodies is a constant. Our pseudotriangulation algorithm is the composition of three independent algorithms:

• (1) an algorithm to compute the convex hull, i.e., the boundary bitangent line segments, of a planar family of pairwise disjoint convex bodies;

• (2) an algorithm to compute a cross-section of the visibility complex of a family of pairwise disjoint convex bodies with constraints; and

• (3) an algorithm to compute the greedy pseudotriangulation associated to a given cross-section of the visibility complex of a family of pairwise disjoint convex bodies with constraints whose set of constraints contains the boundary bitangent line segments of the family of bodies.

Before recalling the definitions of the terms visibility complex, cross-section, and greedy pseudotriangulation, we add to our two (non-restrictive) assumptions concerning the boundaries of the convex bodies—recall that one of these two assumptions says that the boundaries are free of line segments and the other one says that there is exactly one tangent through each boundary point—the assumption that the family of convex bodies has no triple tangent. This additional assumption is not a restriction on the possible input of our algorithm since for any non-simple chirotope there exists a simple chirotope, computable in constant time, such that the non-simple chirotope and the simple chirotope have the same set of free bitangent line segments and the same set of pseudotriangulations; cf. Appendix B.

1.1.4 Visibility Complexes

Let $\mathbb {X}$ be a connected component or a union of connected components of the free space of a given family of pairwise disjoint convex bodies with constraints living in a topological plane $\mathbb {A}$. We denote by $\mathcal {L}(\mathbb{A})$ and $\mathcal {L}^{\operatorname {or}}(\mathbb{A})$ the spaces of lines and directed lines of $\mathbb {A}$ and we take for granted that the canonical projection $\mathcal {L}^{\operatorname {or}}(\mathbb{A}) \rightarrow \mathcal {L}(\mathbb{A})$ is a two-covering. The space $\mathbb {X}$ inherits from the topological point-line incidence geometry of $\mathbb {A}$ a natural partial topological point-line incidence geometry whose system of lines $\mathcal {L}(\mathbb{X})$ is defined as the space of pairs (x,ℓ) where ℓ ranges over the space of lines of $\mathbb {A}$ and x the set of connected components of the pre-image of the line ℓ under the canonical projection $\mathbb{X} \rightarrow\mathbb{A}$, and whose set of incidences is the set of point-line pairs $(p,(x,l)) \in\mathbb{X} \times \mathcal {L}(\mathbb{X})$ with p∈x. Note that the second component ℓ of a pair $(x,\ell) \in \mathcal {L}(\mathbb{X})$ is determined by its first component x unless x is reduced to a point, which happens precisely when x is a cusp point of the boundary of $\mathbb{X}$. Except in the case where $\mathbb {X}$ is the complement of the interior of the convex hull of the bodies, in which case $\mathcal {L}(\mathbb {X})$ is a torus to which is attached, along one of its non trivial closed simple curve, a one-punctured disk, the space of lines of $\mathbb{X}$ has a natural structure of (possibly one-punctured) two-dimensional cell complex: its 1-skeleton is the set of tangents to the boundary of $\mathbb{X}$—which includes the lines through the cusp points of the boundary of $\mathbb{X}$—and its 0-skeleton is the set of bitangents of $\mathbb{X}$. The visibility complex of $\mathbb{X}$ is its space of lines $\mathcal {L}(\mathbb{X})$ endowed with its natural structure of cell complex; furthermore we add to the definition that the one-skeleton of the visibility complex is endowed with the orientation inherited by duality from the orientation of the underlying topological plane; cf. [3, 35, 37]. Similarly we introduce the space $\mathcal {L}^{\operatorname {or}}(\mathbb{X})$ of directed lines of $\mathbb{X}$, endowed with its natural structure of cell complex together with the natural orientation of its one-skeleton inherited by duality from the orientation of the underlying topological plane, and we take for granted that the natural projection $\mathcal {L}^{\operatorname {or}}(\mathbb{X}) \rightarrow \mathcal {L}(\mathbb{X})$ is a two-covering in picture of the two-covering $\mathcal {L}^{\operatorname {or}}(\mathbb{A}) \rightarrow \mathcal {L}(\mathbb{A})$ and that the cell structure on $\mathcal {L}^{\operatorname {or}}(\mathbb{X})$ is regular contrary, in general, to that of $\mathcal {L}(\mathbb{X})$.

Example 1.1

The visibility complex $\mathcal {L}(\mathbb {X})$ of the free space $\mathbb {X}$ of a family of two disjoint convex bodies o _i ,o _j is composed of

• (1) four 0-cells: the four bitangents t ₁,t ₂,t ₃,t ₄ of the family of bodies;

• (2) eight oriented 1-cells: the four connected components of $o_{i}^{*}\setminus\{t_{1},t_{2},t_{3},t_{4}\}$ and the four connected components of $o_{j}^{*}\setminus\{ t_{1},t_{2},t_{3},t_{4}\}$, where $o_{i}^{*}$ denotes the set of tangents to o _i ; and

• (3) five 2-cells: the sets of lines with labels—in the context of a family of convex bodies with empty set of constraints, the label of a directed line is the sequence of bodies intersected by the line ordered as they appear along the line and prefixed or postfixed or both prefixed and postfixed by the symbol ∞ in case the line is (orientation preserving) homeomorphic to ℝ⁺,ℝ⁻ or ℝ endowed with their natural orientations—with labels ij, i∞, j∞, the set of lines with label ∞∞ that separate the two bodies, and the set of lines with label ∞∞ that do not separate the two bodies;

put together as indicated in Fig. 4 where we write i for the bitangent t _i ; this complex is not regular: the boundaries of the 2-cells with label i∞ and j∞ are complete graphs on four elements; and this complex has one end, indicated by a marked point ∞ (red in pdf color) in the figure.

Fig. 4

The visibility complex of the free space of a family of two disjoint convex bodies

Example 1.2

The visibility complex $\mathcal {L}(\mathbb {X})$ of a generic pseudotriangle $\mathbb {X}$ with cusp points a,b,c consists of

• (1) three 0-cells: the tangents t _a ,t _b and t _c at the cusp points a,b, and c;

• (2) six oriented 1-cells: the $x^{*} = \mathcal {L}(x)\setminus\{ t_{x}\}$, x∈{a,b,c}, where $\mathcal {L}(x)$ denotes the set of lines through the point x, and the three connected components α,β and γ of the curve $\mathcal {L}(\partial\mathbb{X})$ of tangent lines to the pseudotriangle minus t _a ,t _b , and t _c ; and

• (3) three 2-cells: the interiors of the $\mathcal {L}(x,x')$ where $\mathcal {L}(x,x')$ denotes the set of lines joining the sides opposite to the pair of cusp points x and x′;

put together as indicated in Fig. 5; again observe that this complex is non regular (its one-skeleton is already non regular); this complex has no end.

Fig. 5

The visibility complex of a generic pseudotriangle

1.1.5 Cross-Sections

The boundary of any bounded 2-cell of $\mathcal {L}^{\operatorname {or}}(\mathbb {X})$—bounded in the sense that the cell contains no end of $\mathcal {L}(\mathbb{X})$—has a unique vertex of outdegree two and a unique vertex of indegree two; therefore one can speak of the source and sink vertices of a 1- or bounded 2-cell of $\mathcal {L}^{\operatorname {or}}(\mathbb{X})$, and one can speak of the left and right boundary chains of a 2-cell. Let $\mathcal {L}(\mathbb {X})^{*}{}\rightarrow \mathcal {L}(\mathbb {X}){}$ be the inverse image of a universal cover $\mathcal {L}^{\operatorname {u}}(\mathbb {A})$ of $\mathcal {L}(\mathbb {A})$ under the natural projection $\mathcal {L}(\mathbb {X})\rightarrow \mathcal {L}(\mathbb {A})$—that is $\mathcal {L}(\mathbb {X})^{*}{}$ is the set of pairs $(v,l) \in \mathcal {L}(\mathbb {X})\times \mathcal {L}^{\operatorname {u}}(\mathbb {A})$ such that the image of v under $\mathcal {L}(\mathbb {X})\rightarrow \mathcal {L}(\mathbb {A})$ coincides with the image of l under $\mathcal {L}^{\operatorname {u}}(\mathbb {A})\rightarrow \mathcal {L}(\mathbb {A})$, and $\mathcal {L}(\mathbb {X})^{*}{} \rightarrow \mathcal {L}(\mathbb {X}){}$ is the first projection, cf. [16, pages 113–114]—let $\mathcal {O}(\mathbb{X})$ be the set of cells of $\mathcal {L}(\mathbb {X})^{*}{}$ endowed with the partial order generated by the relations

$$ \operatorname {sour}(\sigma) \prec\sigma\prec \operatorname {sink}(\sigma) $$

(1)

where σ ranges over the set of 1- and bounded 2-cells of $\mathcal {O}(\mathbb{X})$ and where $\operatorname {sour}(\sigma)$ and $\operatorname {sink}(\sigma)$ denote the source and the sink of the cell σ, let ν be the generator of the automorphism group of the covering $\mathcal {L}(\mathbb {X})^{*}{} \rightarrow \mathcal {L}(\mathbb {X}){}$ defined by the condition that σ≺ν(σ): the shift operator for short, and finally let J be a maximal antichain of $\mathcal {O}(\mathbb{X})$. The cross-section, denoted Γ(J), of the visibility complex of $\mathbb{X}$ at the maximal antichain J is the directed multigraph whose set of arcs is the set of 2-cells of J and whose set of nodes is the set of 0- and 1-cells of J, the source node of an arc being defined as the unique node included in its right boundary (if any) and its sink node being defined as the unique node included in its left boundary (if any).

Example 1.3

Let I be a proper filter of the subposet of 0-cells of $\mathcal {O}(\mathbb {X})$. Then the set of 1- and 2-cells of $\mathcal {O}(\mathbb {X})$ whose sinks belong to I but not their sources is a maximal antichain; the corresponding cross-section is called the canonical cross-section associated with the filter I.

Example 1.4

Figure 6 depicts a family of seven convex bodies of the real affine plane with one constraint (the bodies are numbered from 1 to 7 and the constraint is the undirected version of the right–right bitangent line segment joining the third body of the family to the fourth body) and (an upward drawing of) the canonical cross-section of its visibility complex associated with the filter of the subposet of vertices of $\mathcal {O}(\mathbb {X})$ with angle ≥0. The family of convex bodies is augmented for each 1-cell e of the cross-section with the horizontal line t(e)∈e. The horizontal lines t(e) induce a trapezoidal decomposition of free space whose trapezoids (23 in number) are in one-to-one correspondence with the arcs of the cross-section: 21 of these 23 trapezoids are labeled in the figure and these labels are reported on the corresponding arcs of the cross-section.

Fig. 6

The horizontal cross-section of the visibility complex of a family of seven pairwise disjoint convex bodies with one constraint of the real affine plane

Example 1.5

Figure 7 depicts a family of seven convex bodies of the real affine plane with one constraint (the bodies are numbered from 1 to 7 and the constraint is the undirected version of the right–left bitangent line segment joining the second body of the family to the fourth body) and the canonical cross-section associated with the filter of 0-cells of $\mathcal {O}(\mathbb {X})$ generated by the lift in $\mathcal {L}(\mathbb {X})^{*}{}$ of the principal filter of any left–left lift in $\mathcal {L}^{\operatorname {u}}(\mathbb {A})$ of a left–left boundary bitangent (the one joining the first body to the second body). The family of convex bodies is augmented for each 1-cell e of the cross-section with a line t(e)∈e. The t(e) induce a trapezoidal decomposition of free space whose trapezoids (23 in number) are in one-to-one correspondence with the arcs of the cross-section: nine of these 23 trapezoids are labeled in the figure and these labels are reported on the corresponding arcs of the cross-section.

Fig. 7

The canonical cross-section of the visibility complex of a family of seven pairwise disjoint convex bodies with one constraint of the real affine plane associated with one of its boundary bitangent line segment

1.1.6 Greedy Pseudotriangulations

One of the key results of the theory of visibility complexes is that the set of sink bitangent line segments¹ of the cells of a cross-section of a visibility complex is a pseudotriangulation; cf. [3, Theorem 6, Claim 1]. This pseudotriangulation is called greedy because it can also be defined as the set of bitangent line segments of the sequence v ₁,v ₂,…,v _h of vertices of $\mathcal {O}(\mathbb{X})$ defined inductively by v _i is a ≺-minimal element in the poset of vertices of the filter generated by the cross-section crossing none of the elements of the set {v ₁,v ₂,…,v _i−1}.

Example 1.6

Figure 8 depicts the greedy pseudotriangulations associated with the two cross-sections introduced in Examples 1.4 and 1.5. Some of the labels of the arcs of the cross-sections are reported on the corresponding bitangent line segments of the associated greedy pseudotriangulations.

Fig. 8

The greedy pseudotriangulations associated with the cross-sections of Examples 1.4 and 1.5

1.1.7 Declination of the Main Result

Theorem 1.1 can then be declined as follows.

Theorem 1.2

The convex hull of a planar family of n pairwise disjoint convex bodies presented by its chirotope is computable (under the guise of the circular sequence of boundary bitangent line segments of the family of bodies) in O(nlogn) time and linear space.

Theorem 1.3

The canonical cross-section associated with a given boundary bitangent line segment (as defined in Example 1.5) of the visibility complex of a family of n pairwise disjoint convex bodies with constraints presented by its chirotope is computable in O(nlogn) time and linear space.

Theorem 1.4

The greedy pseudotriangulation associated with a given cross-section of the visibility complex of a family of n pairwise disjoint convex bodies with constraints presented by its chirotope is computable in linear time under the assumptions that the family is well-constrained and that the set of constraints contains the boundary bitangent line segments of the family of bodies.

Of course it is also sensitive to ask if the (cell structure of the) visibility complex of (the free space of) a family of convex bodies with constraints presented by its chirotope is efficiently computable. Under the assumption that the family is well-constrained, a positive answer to that question is given by Angelier and Pocchiola [3, Theorem 1] modulo the efficient computation of a cross-section and the efficient computation of its associated greedy pseudotriangulation. (The notion of chirotope used in [3] is finer than the notion of chirotope that we are using here—however, the algorithmic technique developed in [3, page 117], called the χ ₁-Walk procedure, can be adapted to the present situation; details on this point will be reported in a different paper.) Therefore combining our Theorems 1.2, 1.3, and 1.4 with Theorem 1 of Angelier and Pocchiola [3] we get the following theorem.

Theorem 1.5

The visibility complex of a planar family of n pairwise disjoint convex bodies presented by its chirotope is computable in O(k+nlogn) time and linear working space where k is the size of the visibility complex. A similar result holds for the visibility complex of a family of pairwise disjoint convex bodies with constraints under the assumption that the family is well-constrained.

In particular the well-constrained chapter of the above result can be used to show that the visibility graph of a finite planar family of pairwise interior non-crossing line segments presented by the chirotope of the endpoints of the line segments is efficiently computable; cf. Appendix C.

1.2 Previous Work

The convex hull and pseudotriangulation problems have been addressed in the past only for families of pairwise disjoint convex bodies affine topological planes—strictly speaking the problems have only been studied in the real affine plane, however, it is a simple exercise to adapt the arguments to affine topological planes—the following solutions have been reported: the set of boundary bitangent line segments can be computed as the set of breakpoints of the upper envelope of the support functions of the bodies using a divide-and-conquer algorithm, cf. [43, Chap. 6] and [39], and a pseudotriangulation can be computed using a straight sweep à la Bentley–Ottmann from the positive horizontal direction to the negative horizontal direction of a dynamically changing visibility complex, cf. [36]. Both algorithms run in O(nlogn) time using not only the chirotope of the family of convex bodies but also the direction or slope order on the set of bitangents of the family augmented with a point outside the convex hull of the bodies, an information which is meaningless in a topological plane which is not affine; the situation is even worse for the constrained pseudotriangulation problem since the algorithm uses also the chirotope of the family of bodies and constraints, that is, also the relative positions of the endpoints of the constraints with respect to the bitangents. (To fix the ideas we mention that given four pairwise disjoint ellipses in the real affine plane evaluating the position of an endpoint of a bitangent line segment joining the first two ellipses with respect to a bitangent joining the last two ellipses is out of the reach of the current practical techniques in formal calculus: Gröbner bases and so one [45].) More sophisticated techniques—using even more involved predicates like slicing the bodies—have been developed to design output sensitive convex hull algorithm, cf. [30]. The related but different problem of computing the convex hull of a simple curved polygon is addressed in [5].

We mention that our pseudotriangulation algorithm accepts a larger set of input, uses simpler data structures and simpler geometric predicates, has fewer degenerate cases to handle, and is faster by a logn factor in its main phase (which consists of deriving a pseudotriangulation from a cross-section of the visibility complex of the family of convex bodies with constraints) than the one developed in [36] and currently implemented in the visibility complex package of the CGAL library [2].

For families of points the situation is different: Graham’s scan [18] and Knuth’s two incremental algorithms [25, pages 45–61] compute in O(nlogn) time the convex hull of a family of points using only its chirotope; on the other hand neither Chan’s output sensitive convex hull algorithm [10] nor the one of Kirkpatrick and Seidel [23] are only based on the chirotope since a preliminary step of both algorithms is to compute in linear time an extreme point of the family (the one with minimum horizontal coordinate), a problem known to be open for families of points only given by their chirotopes [25, page 98]. Similarly a greedy pseudotriangulation of a finite planar family of points can be computed in O(nlogn) time using only the chirotope of the family of points as we explain in Appendix D.

1.3 Outline of Our Pseudotriangulation Algorithm

The design and correction of our pseudotriangulation algorithm relies on an extension of the theory of visibility complexes of families of pairwise disjoint convex bodies of the real affine plane to families of pairwise disjoint convex bodies of topological planes and of their branched coverings. In particular our Theorem 1.4 is not only valid for families of pairwise disjoint convex bodies with constraints of topological planes but also for families of pairwise disjoint convex bodies with constraints of branched covering of topological planes (under the mild assumption that the convex bodies cover the branch points of the covering space). A similar observation can be made regarding Theorem 1 of Angelier and Pocchiola [3]. While the use of universal coverings, or portions of universal coverings, in the design of geometric algorithms had already appeared in the early days of the computational geometry literature, e.g., [14, 21], it seems to be the first time that branched coverings are used in the design of a geometric algorithm. (Branched coverings are used in [42] to define the dual Voronoi diagram of a constrained Delaunay triangulation in the plane, but apparently without algorithmic consequences—see also the discussion in [12, page 30].) We refer to [27, page 145], [22], [26, page 18] and the references cited therein for background material on branched coverings.

Our algorithm proceeds in three steps: we first compute the convex hull of the family of convex bodies, then the cross-section of the visibility complex of the family of convex bodies with constraints assigned to a distinguished boundary bitangent line segment, and finally the greedy pseudotriangulation associated with that cross-section, that is, the set of sinks of its 2-cells, cf. [36, Theorem 12] and more generally [3, Theorem 6, Claim 1] in the case where we look for a constrained pseudotriangulation.

1.3.1 Convex Hull Algorithm

Our convex-hull algorithm is a sweep of a connected 4-sheeted branched covering of the underlying plane ramified over any interior point of an arbitrarily distinguished body: we sweep the 4-sheeted covering surface with a half-line whose supporting line is a left tangent at the origin of the half-line to the lift of the distinguished body. Any body, except the distinguished one, has four lifts in the 4-sheeted covering surface; we only keep the lifts either lying in one of the first three sheets, either straddling the first two sheets or the second and third sheets or the last two sheets, as illustrated in Fig. 9 where the bodies numbered 1,3,6 and 7 are lifted only in the first three sheets and where the bodies numbered 2 and 5 are lifted astride the first two sheets, the second and third sheets, the last two sheets but not astride the last and first sheets. The sweep starts at a boundary tangent and induces a total order on the lifted bodies with the property that a body contributes to one or zero connected piece to the boundary of its convex hull with its predecessors in the total order. During the sweep we maintain the convex hull of the lifts of the bodies that have been entirely swept or partially swept by the sweeping half-line; the convex hull of the family of bodies is then extracted from the convex hull of the lifts, as illustrated in Fig. 9 where one can read the convex hull of the family of bodies as the boundary bitangents of the lifts drawn with a bold line.

Fig. 9

The computation of the convex hull of a planar family of pairwise convex bodies presented by its chirotope goes through the computation of the convex hull of a certain family of pairwise disjoint convex bodies of a 4-sheeted branched covering surface with one branch point of the underlying plane of the family of convex bodies

1.3.2 Cross-Section Algorithm

Our cross-section algorithm is again a sweep but now a simple sweep of the convex hull of the bodies by a half-line whose supporting line is a left tangent at the origin of the half-line to one of the bodies appearing on the boundary of the convex hull—a boundary body, for short. The sweep starts at one of the boundary bitangent line segments leaving the distinguished boundary body. During the sweep we construct the canonical cross-section of the visibility complex of the family of convex bodies with constraints assigned to the distinguished boundary bitangent line segment, cf. Example 1.5. The method presents some interesting and novel features due to the fact that the relative positions of the constraints with respect to the bitangents are not completely determined by the chirotope of the convex bodies. It is also interesting to mention that this second step is implementable in O(nlogn) without restriction on the possible sets of constraints.

1.3.3 Greedy Pseudotriangulation Algorithm

Our third and last algorithm—which consists of deriving the greedy pseudotriangulation associated to a given cross-section of the visibility complex of a family of pairwise disjoint convex bodies with constraints whose set of constraints contains the boundary bitangent line segments of the bodies—is the most elaborate and fully benefits from the idea of using branched coverings. A preliminary version of this third algorithm—of which the idea of using branched coverings was unfortunately missing—was discussed several years ago by the second author of the paper with his PhD student Pierre Angelier, see [1, pages 83–92] and compare with [37, Appendix A].

We define a partial order < on the set of 2-cells σ of the input cross-section whose sink bitangent line segment t(σ) is not a constraint (and thus not a boundary bitangent line segment), and for each σ we define a pair of adjacent pseudotriangles, called the ${\mathcal{A} \mathcal{B}}$-pseudotriangles of σ, made with the t(σ′), σ′<σ, and with auxiliary bitangent line segments s _j (σ), 1≤j≤σ ^∗, such that a representation of the ${\mathcal{A} \mathcal{B}}$-pseudotriangles of σ by a linked structure $\mathcal{R}_{\sigma}$—that is, collections of nodes interconnected by pointers; cf. [44, page 8]—is computable in constant amortized time and such that t(σ) is computable as the bitangent line segment joining the ${\mathcal{A} \mathcal{B}}$-pseudotriangles of σ in constant amortized time starting from the knowledge of the linked structure $\mathcal{R}_{\sigma}$.

A key feature of our method is that the ${\mathcal{A} \mathcal{B}}$-pseudotriangles are defined as projections in the plane of pseudotriangles of pseudotriangulations of sets of lifts of bodies in certain branched coverings of the plane. (Some of the s _j (σ), 1≤j≤σ ^∗, are computed by a recursive application of the procedure to compute the t(σ).) More precisely, given a finite family of pairwise disjoint convex bodies with constraints (including the boundary bitangent line segments of the convex bodies) of a branched covering $\mathbb {B}_{}$ of a topological plane $\mathbb {A}$, we associate to each bounded 2-cell σ of its visibility complex whose source bitangent line segment is not a constraint a pseudoquadrangle containing ⋃σ, called the ${\mathcal{H}}$-pseudoquadrangle of σ and denoted $\operatorname {\mathcal {H}}(\sigma)$, whose diagonals are the source and the sink bitangent line segments of σ; pseudoquadrangle from which we derive, once a cross-section Γ containing σ is chosen, a pair of pseudotriangles adjacent along the source bitangent line segment of σ, called the ${\mathcal{A}\mathcal{B}_{0}}$-pseudotriangles of σ, with the property that the bitangent line segment joining the ${\mathcal{A}\mathcal{B}_{0}}$-pseudotriangles of σ is the sink bitangent line segment of σ; the definition of the ${\mathcal{A}\mathcal{B}_{0}}$-pseudotriangles depends on the type of σ in Γ which is a pair ij, i,j∈{1,2,3}, that encodes the position of the source and sink nodes of σ in the decomposition of the left and right boundaries of σ into convex chains (three in number at most). Then we assign to the 2-cell σ, element of the cross-section Γ, a 2-cell μ(σ), element of a certain cross-section μ(Γ) of the visibility complex of a certain family of convex bodies and constraints of a certain branched covering $\mu (\mathbb {B}_{})$ of the topological plane $\mathbb {A}$—obtained as connected sum of $\mathbb {B}_{}$ and copies of the plane $\mathbb {A}$ as indicated in Fig. 10—so that, among other things, σ and μ(σ) have the same sink. The ${\mathcal{A} \mathcal{B}}$-pseudotriangles of σ are then defined as the ${\mathcal{A}\mathcal{B}_{0}}$-pseudotriangles of μ(σ). The correction of the method relies on several new properties of cross-sections of visibility complexes.

Fig. 10

Given a branched covering $\mathbb {B}_{}$ of a topological plane $\mathbb {A}$ and a simple oriented curve γ in $\mathbb {B}_{}$ homeomorphic to its projection γ′ in $\mathbb {A}$ under the covering map $\mathbb {B}_{}\rightarrow \mathbb {A}$ we construct a new branched covering $\lambda ^{}_{\gamma}{(\mathbb {B}_{})}$ of $\mathbb {A}$ as follows. Cut $\mathbb{C} = \mathbb {B}_{} \sqcup \mathbb {A}$ along γ and γ′, call ℂ _γ the resulting surface and q:ℂ _γ →ℂ the induced projection. Then we define $\lambda ^{}_{\gamma}{(\mathbb {B}_{})}$ as the quotient space of ℂ _γ by identification of the left lift of γ under q with the right lift of γ′ under q as well as the right lift of γ under q with the left lift of γ′ under q. The operator μ is defined as the composition of several $\lambda ^{}_{\gamma}{}$ operators

1.4 Organization of the Paper

In the next section we extend the theory of pseudotriangulations and visibility complexes to the setting of branched coverings of topological planes (no proofs will be given since one can adapt easily to that setting the proofs given in [3, 36, 37]), we establish several new properties of cross-sections of visibility complexes, and we introduce the main ingredients of our pseudotriangulation algorithm mentioned in the previous sections. In the third section we describe our pseudotriangulation algorithm, we analyze its complexity, and we conclude in the fourth and last section.

2 Visibility in Branched Coverings

In this section we extend the theory of pseudotriangulations and visibility complexes to the setting of branched coverings of topological planes; we establish several new properties of cross-sections of visibility complexes; and we introduce the key ingredients of our algorithm mentioned in the introduction: ${\mathcal{H}}$-pseudoquadrangles, ${\mathcal{A}\mathcal{B}_{0}}$-pseudotriangles, and ${\mathcal{A} \mathcal{B}}$-pseudotriangles. For the sake of simplicity and clarity we only went over the case where the set of constraints is empty, the general case can be treated very similarly using the definition of visibility complexes of families of pairwise disjoint convex bodies with constraints given in the introduction.

Let ${\mathcal{D}}$ be a finite family of pairwise disjoint convex bodies of a finite connected branched covering space $\mathbb {B}_{}$ of an oriented topological plane $\mathbb {A}$ equipped with the partial topological point-line incidence structure, with singularities at the branch points, inherited from the point-line incidence structure of $\mathbb {A}$. We assume that the boundaries of the convex bodies are free of line segments, that there is exactly one tangent line through each boundary point, that the bodies surround the branch points of the covering space, and we use the following associated terminology and notations: free space is the complement of the interiors of the bodies; a bitangent line segment is a closed line segment of free space tangent to two bodies at its endpoints; a boundary bitangent line segment is a bitangent line segment contained in the boundary of the convex hull of the bodies; all other bitangent line segments are said to be interior bitangent line segments; a primitive arc is a connected component of the boundary of the bodies minus the bitangent line segments; $h_{{\mathcal{D}}}$ is the number of boundary bitangent line segments; $n_{{\mathcal{D}}}$ is the sum of the orders of the branch points plus the number of bodies surrounding no branch points; $k_{{\mathcal{D}}}$ is the number of sheets of the branched covering space.

2.1 Pseudotriangulations

A pseudotriangulation is a maximal, for the inclusion relation, collection of pairwise interior non-crossing bitangent line segments. As in the case where the covering map $\mathbb {B}_{} \rightarrow \mathbb {A}$ is the identity map of the real affine plane, a pseudotriangulation induces a subdivision of free space whose bounded regions are pseudotriangles, that is, subsets of free space homeomorphic via the covering map to pseudotriangles of the topological plane.

Theorem 2.1

Let $\mathcal{T}$ be a pseudotriangulation of ${\mathcal{D}}$. Then the bounded faces of the subdivision of free space induced by $\mathcal{T}$ are pseudotriangles, their number is $2n_{{\mathcal{D}}}-2k_{{\mathcal{D}}}$ and the size of $\mathcal{T}$ is $3n_{{\mathcal{D}}}-3k_{{\mathcal{D}}}$. Furthermore any interior bitangent line segment of $\mathcal{T}$ can be flipped, that is, replaced by an interior bitangent line segment to obtain a new pseudotriangulation.

Proof

One can repeat the proof given for the real affine plane in [37] since the lines of a topological plane—and consequently the lines of free space—are geodesics for an ad hoc metric on the topological plane; cf. [9, Theorem 11.2, page 56]. □

Two pseudotriangulations are said to be adjacent (or related by a flip) if they differ by a single (necessarily interior) bitangent line segment. The adjacency graph on the set of pseudotriangulations is a connected regular graph of degree $3n_{{\mathcal{D}}}-3k_{{\mathcal{D}}}- h_{{\mathcal{D}}}$. More generally the collection, ordered by inclusion, of subsets of pairwise interior non-crossing free interior bitangent line segments is a strongly flag-connected pure simplicial complex of dimension $3n_{{\mathcal{D}}}-3k_{{\mathcal{D}}}- h_{{\mathcal{D}}}$ which satisfies the diamond property. This simplicial complex will be called thereafter the complex of pseudotriangulations of the family of convex bodies.

Example 2.1

Figure 11 depicts a family of two convex bodies of a 2-sheeted branched covering of $\mathbb {A}$ with two branch points (the two sheets are obtained by cutting the covering space along the two line segments joining the two branch points). Its complex of pseudotriangulations is the cocube of dimension 2. More generally the complex of pseudotriangulations of a family of two convex bodies of a n-sheeted covering surface of the plane with two branch points is the cocube of dimension n.

Fig. 11

A family of two disjoint convex bodies of a 2-sheeted branched covering with two branch points of the real affine plane together with its eight bitangents

2.2 Visibility Complexes

We now assume that there is no tritangent. Free space in denoted $\mathbb {F}_{}$. The space $\mathbb {F}_{}$ inherits from the point-line incidence structure of $\mathbb {A}$ a natural partial point-line incidence structure whose system of lines is defined as the space of connected components of the pre-images of the lines of $\mathbb {A}$ under the canonical projection $\mathbb{X} \rightarrow\mathbb{A}$, and whose set of incidences is the set of point-line pairs (p,x) with p∈x. The label of a directed line of $\mathbb {F}_{}$ is the sequence of bodies intersected by the line ordered as they appear along the line and prefixed or postfixed or both prefixed and postfixed with the symbol ∞ in case the line is (orientation preserving) homeomorphic to the curves ℝ⁺, ℝ⁻ or ℝ endowed with their natural orientations. A directed line of $\mathbb {F}_{}$ touching tangentially a body o is called a left or right tangent to o depending on whether o lies, locally around the touching point, on the left side or on the right side of the line. A directed line of $\mathbb {F}_{}$ joining tangentially a body o to a body o′ is said to leave o and to reach (or enter) o′ and is called a left–left, left–right, right–left, or right–right bitangent depending on whether the line is a left tangent to both o and o′, a left tangent to o and a right tangent to o′, a right tangent to o and a left tangent to o′, or a right tangent to both o and o′. The sets of left and right tangents to a body are simple closed curves to which we assign the orientation inherited by duality from the orientation of the ground topological plane $\mathbb {A}$.

2.2.1 Cell Structure

Let $\mathbb {V}_{} = \mathbb {V}^{2}_{}$ be the space of directed lines of $\mathbb {F}_{}$, $\mathbb {V}^{1}_{}$ its space of left and right tangents, and $\mathbb {V}^{0}_{}$ its space of left–left, left–right, right–left and right–right bitangents. The operator that reverses the direction of a directed line is denoted ι and we take for granted that the natural projection ${\mathbb {V}_{}} \rightarrow{ \mathbb {V}_{}/\iota }$ is a 2-covering. The increasing sequence

$$ \mathbb {V}^0_{} \subset \mathbb {V}^1_{} \subset \mathbb {V}^2_{} = \mathbb {V}_{} $$

(2)

is, modulo the adjunction of a point at infinity in each connected component of $\mathbb {V}_{}\setminus \mathbb {V}^{1}_{}$ whose topological closure is non-compact, the sequence of 0-, 1-, and 2-skeletons of a natural structure of finite 2-dimensional regular cell complex on $\mathbb {V}_{}$: since the curves of tangents to the bodies are oriented curves one can speak of the source and sink vertices or 0-cells of a 1-cell; as usual a chain of $\mathbb {V}^{1}_{}$ is a sequence of 0- and 1-cells such that the predecessor (if any) and the successor (if any) of a 1-cell are its source and its sink, respectively; as usual the points added at infinity are called the ends of $\mathbb {V}_{}$; and a 2-cell is said bounded if it contains no end. This complex satisfies the following properties:

• (1) A 0-cell is the source and the sink of two 1-cells;

• (2) The boundary of a bounded 2-cell is composed of two chains that share the same source/sink, called the source/sink of the 2-cell. Conversely any vertex is the source/sink of a bounded 2-cell. By convention the right/left boundary chain of a bounded 2-cell σ with source v, denoted $\operatorname {rc}(\sigma)/\operatorname {lc}(\sigma)$, is the boundary chain of σ whose first 1-cell is supported by the curve of tangents to the body reached/left by v and supporting v;

• (3) The boundary of an unbounded 2-cell is composed of a single chain; An unbounded 2-cell is said to be left or right unbounded depending on whether its boundary is composed of right or left tangents, respectively. The number of left unbounded 2-cells and the number of right unbounded 2-cells are both equal to the number of connected components of the complement of the convex hull of the family of convex bodies;

• (4) A 1-cell is incident to three 2-cells with labels the subsequences of length two of its label; The three 2-cells incident to the 1-cell σ of $\mathbb {V}_{}$ with label ijk are denoted σ _α , $\alpha\in\{\operatorname {r},\operatorname {l}, \operatorname {b},\operatorname {f}\}$, according to the following rule: the 2-cells with label ij and jk are denoted $\sigma_{\operatorname {b}}$ and $\sigma_{\operatorname {f}}$, respectively; and the remaining 2-cell, whose label is ik, is denoted $\sigma_{\operatorname {r}}$ or $\sigma_{\operatorname {l}}$ depending on whether the lines of σ are left or right tangents, as illustrated in Fig. 12;

  Fig. 12

  

  A left 1-cell σ with label ijk is incident to three 2-cells $\sigma _{\operatorname {b}},\sigma _{\operatorname {f}}$ and $\sigma _{\operatorname {r}}$ with labels ij,jk and ik, respectively. Similar notations are used for right 1-cells

• (5) A 0-cell is incident to four 1-cells with labels the subsequences of length 3 of its label;

• (6) A 0-cell is incident to six 2-cells with labels the subsequences of length 2 of its label. The six 2-cells incident to the 0-cell σ of $\mathbb {V}_{}$ with label ijkl are denoted σ _α , $\alpha\in \varLambda = \{\epsilon ,\operatorname {s},\operatorname {r},\operatorname {l}, \operatorname {b},\operatorname {f}\}$ according to the following rules:

  • (a) $\sigma_{\operatorname {b}}$ is the 2-cell with label ij;

  • (b) $\sigma_{\operatorname {f}}$ is the 2-cell with label kl;

  • (c) σ _ϵ is the 2-cell with label jk,jl,il, or ik depending on whether σ is a left–right, left–left, right–left or right–right bitangent;

  • (d) $\sigma_{\operatorname {s}}$ is the 2-cell with label il,ik,jk, or jl depending on whether σ is a left–right, left–left, right–left or right–right bitangent;

  • (e) $\sigma_{\operatorname {r}}$ is the 2-cell with label ik,il,jl, or jk depending on whether σ is a left–right, left–left, right–left or right–right bitangent;

  • (f) $\sigma_{\operatorname {l}}$ is the 2-cell with label jl,jk,ik, or il depending on whether σ is a left–right, left–left, right–left or right–right bitangent, as illustrated in Fig. 13.

    Fig. 13

    

    A left–right vertex σ with label ijkl is incident to six 2-cells $\sigma _{\operatorname {b}}, \sigma _{\operatorname {f}}, \sigma _{\operatorname {l}},\sigma _{\operatorname {r}}$, σ _ϵ and $\sigma_{\operatorname {s}}$ with labels ij,kl,ik,jl,jk,il, respectively. Similar notations are used for left–left, right–left and right–right vertices

By definition the visibility complex of the family of pairwise disjoint convex bodies ${\mathcal{D}}$ is the regular cell complex $\mathbb {V}^{0}_{} \subset \mathbb {V}^{1}_{}\subset \mathbb {V}^{2}_{} = \mathbb {V}_{}$ endowed with the orientation of its one-skeleton $\mathbb {V}^{1}_{}$ inherited from the orientation of the ground topological plane $\mathbb {A}$.

Example 2.2

The visibility complex a family of two disjoint convex bodies o _i ,o _j of $\mathbb {A}$ is composed of eight 0-cells, 16 (oriented) 1-cells and ten 2-cells (the sets of lines with labels ij, ji, i∞, ∞i, j∞, ∞j, and ∞∞ four times) put together as indicated in Fig. 14 where, by convention, the left boundary chain of a bounded 2-cell is above its right boundary chain (thus, one can read on the figure that the right boundary chain of the 2-cell with label ij is $1j_{1}3'i'_{3}4'$ and that its left boundary chain is 1i ₁2j ₂4′); in the introduction section we observed that the quotient of this complex under ι is not regular.

Fig. 14

The visibility complex of a planar family of two disjoint convex bodies

Example 2.3

Figure 15 depicts the cell decomposition of the quotient under ι of the visibility complex of a family of two convex bodies of a 2-sheeted branched covering of $\mathbb {A}$ with two branch points (the two sheets are obtained by cutting the covering space along the two line segments joining the two branch points).

Fig. 15

The quotient under the operator that reverses the direction of a directed line of the visibility complex of a family of two disjoint convex bodies of a 2-sheeted branched covering of a plane with two branch points

2.2.2 Horizon Operators

We now describe, in preparation for the section on ${\mathcal{A} \mathcal{B}}$-pseudotriangles, the boundary chains of the 1- and 2-cells in terms of the operators, denoted φ _α , $\alpha \in\{\epsilon ,\operatorname {s},\operatorname {r},\operatorname {l}, \operatorname {b},\operatorname {f}\}$, that assign to a 0- or 1-cell σ the sink vertices of its incident 2-cells σ _α (if defined); in particular, $\varphi _{\operatorname {s}}(v)$ is the sink of the 2-cell with source v, φ _ϵ (v) is the identity operator, and, for a left 1-cell e, supported by the curve of left tangents to the body o, the bitangent $\varphi _{\operatorname {f}}(e)$ is the first bitangent leaving o encountered when we traverse the curve of left tangents to o starting from e. Note that $\varphi _{\operatorname {l}}$ and $\varphi _{\operatorname {f}}$ are the conjugates of $\varphi _{\operatorname {r}}$ and $\varphi _{\operatorname {b}}$ under the reorientation operator ι, that is, $\iota \circ \varphi _{\operatorname {l}}= \varphi _{\operatorname {r}}\circ \iota$, $\iota \circ \varphi _{\operatorname {f}}= \varphi _{\operatorname {b}}\circ \iota$. We name these operators the horizon operators in reference to the operators underlying the definition of the horizon trees of Edelsbrunner and Guibas [13]. For example the table of the horizon operators on the set of bitangents of the visibility complex of two convex bodies of the plane is the following:

$$\begin{array}{l|l@{\quad}l@{\quad}l@{\quad}l@{\quad}l@{\quad}l@{\quad}l@{\quad}l} & 1& 2& 3& 4& 1'& 2'& 3'& 4'\\[-1pt] \hline\noalign{\vspace{-2pt}} \iota & 1'& 2'& 3'& 4'& 1& 2& 3& 4\\ \varphi _{\operatorname {s}}& 4'& 3'& 2'& 1& 4& 3& 2& 1'\\ \varphi _{\operatorname {l}}& 2& \mbox{--} & \mbox{--} & 2'& 3& 4& 4'& 3'\\ \varphi _{\operatorname {r}}& 3'& 4& 1'& 3& 2'& \mbox{--} & \mbox{--} & 2\\ \varphi _{\operatorname {f}}& 2'& 2'& 2& 2& 3'& 3'& 2'& 2'\\ \varphi _{\operatorname {b}}& 3& 3& 2& 2& 2& 2& 2'& 2'\\ \end{array} $$

where – stands for undefined and where we use the notations of Example 2.2. The proofs of the two following theorems are easy (using continuity arguments) and are left to the reader.

Theorem 2.2

Let e be a left 1-cell supported by the curve of left tangents to the body o. Then $\operatorname {sink}(e) = \varphi _{\operatorname {r}}(e)$ if $\operatorname {sink}(e)$ reaches o; otherwise $\operatorname {sink}(e) = \varphi _{\operatorname {f}}(e)$. Furthermore $\varphi _{\operatorname {f}}(e)$ is the first 0-cell leaving o encountered when we traverse its curve of left tangents starting from e. A similar result holds for right 1-cells using conjugation under ι.

Theorem 2.3

Let σ be a bounded 2-cell of $\mathbb {V}_{}$, let o be the body that the source of σ reaches, let o′ be the body that the sink of σ leaves, let c be the curve of tangents to o supporting the source of σ, and let c′ be the curve of tangents to o′ supporting the sink of σ. Then the right boundary chain of σ is the concatenation of three (convex) chains $\operatorname {rc}_{1}(\sigma), \operatorname {rc}_{2}(\sigma)$ and $\operatorname {rc}_{3}(\sigma)$ whose atoms a, except $\operatorname {sour}(\sigma)$ and $\operatorname {sink}(\sigma)$, are characterized by $\varphi _{\operatorname {b}}(a)$, $\varphi _{\operatorname {l}}(a)$ and $\varphi _{\operatorname {f}}(a) = \operatorname {sink}(\sigma)$, respectively. Furthermore

• (1) if c is the curve of right tangents to the body o then $\operatorname {rc}_{1}(\sigma) = \operatorname {sour}(\sigma)$; otherwise

  $$\operatorname {rc}_{1}(\sigma)= \operatorname {sour}(\sigma)e_{10}v_{11}e_{11} \ldots e_{1k_1} \quad(k_1 \geq0), $$

  where $v_{11}v_{12}\ldots v_{1k_{1}}$ is the maximal sequence of consecutive 0-cells leaving o that follow $\operatorname {sour}(\sigma)$ on c;

• (2) if c′ is the curve of right tangents to the body o′ then $\operatorname {rc}_{3}(\sigma) = \operatorname {sink}(\sigma)$; otherwise

  $$\operatorname {rc}_{3}(\sigma)= e_{3k_3}\ldots e_{31}v_{31}e_{30} \operatorname {sink}(\sigma) \quad(k_3 \geq0), $$

  where $v_{3k_{3}}\ldots v_{31}$ is the maximal sequence of consecutive 0-cells reaching o′ that precede $\operatorname {sink}(\sigma)$ on c′;

• (3) if c=c′ then c is the curve of right tangents to o and $\operatorname {rc}_{2}(\sigma)$ is a 1-cell whose source and sink are the source and the sink of σ, respectively; otherwise

  $$\operatorname {rc}_{2}(\sigma)= e_{20}v_{21}e_{21}v_{22} \ldots v_{2k_2} e_{2k_2} \quad(k_2 \geq1), $$

  where

  • (a) e ₂₀ is the empty chain if and only if c is a curve of left tangents;

  • (b) $e_{2k_{2}}$ is the empty chain if and only if c′ is a curve of left tangents;

  • (c) v ₂₁ is the first 0-cell reaching o that follows $\operatorname {sour}(\sigma)$ on c;

  • (d) $v_{2k_{2}}$ is the first 0-cell leaving o′ that precedes $\operatorname {sink}(\sigma)$ on c′;

  • (e) $v_{2,i+1} = \varphi _{\operatorname {b}}(v_{2i})$ and the e _2i are right 1-cells.

A similar result holds for the left boundary chain of σ using conjugation under ι.

Example 2.4

The convex decompositions of the left and right boundary chains of the bounded 2-cells of the visibility complex of two convex bodies of the plane are given in Table 1, where we use the notations of Example 2.2.

Table 1 Refers to Example 2.4

Example 2.5

Consider the family of seven convex bodies o ₁,o ₂,…,o ₇ of the real affine plane depicted in Fig. 16 and let σ be the 2-cell of its visibility complex that contains the directed line labeled σ. Then, using the notations $b_{ij}, b_{\overline{i}j}, b_{i\overline{j}}, b_{\overline{ij}}$ for the left–left, right–left, left–right, right–right bitangents joining o _i to o _j , its source and sink are the bitangents b ₂₁ and $b_{\overline {7}\overline{1}}$ and the convex decompositions of its left and right boundary chains are given in Table 2, where we only indicate the bitangents of the chains.

Fig. 16

The bitangent line segments of the left and right boundary chains of a bounded 2-cell of the visibility complex of a family of seven convex bodies

Table 2 Refers to Example 2.5

2.2.3 Greedy Pseudotriangulations

Let $\mathbb {L}$ be the set of directed lines of $\mathbb {A}$. Let $\mathbb {W}_{} \rightarrow \mathbb {V}_{}$ be the inverse image of a universal cover $\widehat {\mathbb {L}}$ of $\mathbb {L}$ under the natural projection $\mathbb {V}_{} \rightarrow \mathbb {L}$—that is, $\mathbb {W}_{}$ is the set of pairs $(v,l) \in \mathbb {V}_{}\times \widehat {\mathbb {L}}$ such that the image of v under $\mathbb {V}_{} \rightarrow \mathbb {L}$ coincides with the image of l under $\widehat {\mathbb {L}} \rightarrow \mathbb {L}$, and $\mathbb {W}_{} \rightarrow \mathbb {V}_{}$ is the first projection, cf [16, pages 113–114]—let $\mathcal {O}$ be the set of cells of $\mathbb {W}_{}$ endowed with the partial order generated by the relations

$$ \operatorname {sour}(\sigma) \prec\sigma\prec \operatorname {sink}(\sigma) $$

(3)

where σ ranges over the set of 1- and bounded 2-cells of $\mathcal {O}$ and where $\operatorname {sour}(\sigma )$ and $\operatorname {sink}(\sigma)$ stand, respectively, for the source and the sink of σ. The sets of left and right unbounded 2-cells of $\mathbb {W}_{}$ are denoted $\hat {\mathbf {0}}$ and $\hat {\mathbf {1}}$, respectively; note that the elements of $\hat {\mathbf {0}}$ and $\hat {\mathbf {1}}$ are isolated elements in $\mathcal {O}$ and that the sizes of $\hat {\mathbf {0}}$ and $\hat {\mathbf {1}}$ are both equal to twice the number of sheets of the branched covering space $\mathbb {B}_{}$. Finally we denote by ν the generator of the (infinite cyclic) automorphism group of the covering $\mathbb {W}_{} \rightarrow \mathbb {V}_{}/\iota$ defined by the condition that σ≺ν(σ), the shift operator for short, and we keep the same symbol to denote a horizon operator and its lift in $\mathbb {W}_{}$; thus $\varphi _{\operatorname {s}}$ is the map that assigns to a vertex v of $\mathcal {O}$ the sink of the 2-cell of $\mathcal {O}$ whose source is v. Two vertices of $\mathcal {O}$ are said crossing if their corresponding bitangent line segments are crossing.

Theorem 2.4

([3, Theorem 5] and [36, Lemma 8])

Two crossing vertices are comparable with respect to the partial order ≺ and the map $\varphi : \mathcal {O}^{0} \rightarrow \mathcal {O}^{0}$ that associates with $v\in \mathcal {O}^{0}$ the minimum element of the set of $u\in \mathcal {O}^{0}$ such that u crosses v and v≺u is well-defined, one-to-one and onto. Furthermore if v is an interior vertex then $\varphi (v) = \varphi _{\operatorname {s}}(v)$; otherwise φ(v)=ν(v).

Let J be a maximal antichain of $\mathcal {O}$, let J ⁺ be the filter of cells $z \in \mathcal {O}$ such that x⪯z for some x∈J, and let

$$ \operatorname {G}(J) = \bigcup_{i\geq1} B_i(J) $$

(4)

where B _i (J) is the set of minimal elements of the set of vertices of J ⁺ that do not cross any element of $\bigcup_{1}^{i-1} B_{j}(J)$ where as usual $\bigcup_{1}^{0} B_{j}(J)=\emptyset$. We denote by $\operatorname {b}$ the operator that assigns to a vertex of $\mathcal {O}$ its corresponding bitangent line segment.

Theorem 2.5

([3, Theorem 5] and [36, Theorem 12])

Let J be a maximal antichain of  $\mathcal {O}$. Then $\operatorname {b}\circ \operatorname {G}(J)$ is a well-defined pseudotriangulation and

$$ \operatorname {G}(J) = J^{+}_0\setminus \varphi \bigl( J^{+}_0\bigr) = \mathcal {V}(J) + \mathrm{sink}\bigl( \mathcal {F}^{\circ }(J)\bigr) $$

(5)

where $J^{+}_{0}$ is the set of vertices of J ⁺, $\mathcal {V}(J)$ is the set of 0-cells of J, and $\mathcal {F}^{\circ }(J)$ is the set of bounded 2-cells of J minus the $\sigma_{\operatorname {f}}$ and $\sigma'_{\operatorname {b}}$ where σ ranges over the set of right–right boundary 0-cells and right boundary 1-cells of J and where σ′ ranges over the set of left–left boundary 0-cells and left boundary 1-cells of J.

The pseudotriangulation $\operatorname {G}(J)$ is called the greedy pseudotriangulation at J.

We describe, again in preparation for the section on ${\mathcal{A} \mathcal{B}}$-pseudotriangles, the boundary chains of the pseudotriangles of the greedy pseudotriangulations in terms of the horizon operators. Let J be a maximal antichain of $\mathcal {O}$. Let v be a minimal element of the subposet of vertices of J ⁺ that is not a left–left boundary bitangent and let $\operatorname {R}(v)$ be the pseudotriangle of the pseudotriangulation $\operatorname {b}\circ \operatorname {G}(J)$ lying locally on the right side of the bitangent line segment $\operatorname {b}(v)$. One can easily show that the pseudotriangle $\operatorname {R}(v)$ is independent of the choice of the maximal antichain J. Walking in counterclockwise order along the boundary of $\operatorname {R}(v)$ starting at the tail of $\operatorname {b}(v)$ we traverse successively four convex chains $\operatorname {R}^{j}(v)$ (j=1,2,3,4). A description of these chains in terms of horizon operators is given in the following theorem where $\overline {\varphi }_{\alpha }$ denotes the conjugate of the operator φ _α under $\operatorname {b}$.

Theorem 2.6

[3, Theorem 10]

Let v be a bitangent that is not a left–left boundary bitangent and let

$$\operatorname {R}^j(v) = e_{j0}v_{j1}e_{j1}, \ldots, v_{jk_j}e_{jk_j}, \quad k_j \geq0 $$

where v _jk stands for a bitangent line segment and e _jk for an arc. Then

• (1) $v_{11} = \operatorname {b}(v)$ and $v_{1,j+1} = \overline {\varphi }_{\operatorname {f}}(v_{1j})$;

• (2) $v_{31} = \overline {\varphi }_{\operatorname {b}}(v_{11})$ and $v_{3,i+1} = \overline {\varphi }_{\operatorname {f}}(v_{3i})$ (assuming that v ₃₁ is well-defined);

• (3) $v_{21} = \overline {\varphi }_{\operatorname {r}}(v_{11})$ and $v_{2,i+1} = \overline {\varphi }_{\operatorname {b}}(v_{2i})$ (assuming that v ₂₁ is well-defined);

• (4) $\overline {\varphi }(v)$ leaves an arc of $\operatorname {R}^{2}(v)$ or the first arc of $\operatorname {R}^{3}(v)$.

2.2.4 Cross-Sections

Let J be a maximal antichain of $\mathcal {O}$ and let $\mathcal {V}(J)$, $\mathcal {E}(J)$, $\mathcal {F}(J)$, and $\mathcal {U}(J)$ be its sets of 0-, 1-, bounded and unbounded 2-cells. Using the simple fact that a maximal antichain and a maximal chain intersect in a single element one can easily check that

• (1) $\mathcal {U}(J)$ is the whole set of unbounded 2-cells and its size is $2k_{{\mathcal{D}}}$;

• (2) for any bounded 2-cell σ of J there is exactly one atom (a 0- or 1-cell) of its right/left boundary chain—denoted $\operatorname {bot}_{J}(\sigma)$/$\operatorname {top}_{J}(\sigma)$ thereafter—that belongs to J;

• (3) for any left/right unbounded 2-cell σ of J there is exactly one atom (a 0- or 1-cell) of its right/left boundary chain—denoted $\operatorname {bot}_{J}(\sigma)$/$\operatorname {top}_{J}(\sigma)$ thereafter—that belongs to J;

• (4) the 2-cells of J are exactly the $\sigma_{\operatorname {r}},\sigma_{\operatorname {f}}, \sigma_{\operatorname {l}}$, and $\sigma_{\operatorname {b}}$, where σ ranges over $\mathcal {V}(J)+ \mathcal {E}(J)$ and where by convention we ignore $\sigma_{\operatorname {r}}$ or (exclusive) $\sigma_{\operatorname {l}}$ if one of them is not defined, that is, if σ is a right 1-cell or a left 1-cell;

• (5) the size of $\mathcal {E}(J)$ is $2 n_{{\mathcal{D}}} - 2 \#\mathcal {V}(J)$;

• (6) the size of $\mathcal {F}(J)$ is $3n_{{\mathcal{D}}} - k_{{\mathcal{D}}} - \# \mathcal {V}(J)$.

The cross-section of the visibility complex of the family of convex bodies ${\mathcal{D}}$ at the maximal antichain J, denoted Γ(J), is the directed multigraph whose set of nodes is the set of 0- and 1-cells of J and whose set of arcs is the set of 2-cells σ of J directed from $\operatorname {bot}_{J}(\sigma)$ to $\operatorname {top}_{J}(\sigma)$. We use the notation $\mathcal {F}_{ij}(J)$, i,j∈{1,2,3}, for the set of $\sigma\in \mathcal {F}(J)$ such that $\operatorname {bot}_{J}(\sigma) \in \operatorname {rc}_{i}(\sigma)$, $\operatorname {top}_{J}(\sigma ) \in \operatorname {lc}_{j}(\sigma)$, and both $\operatorname {bot}_{J}(\sigma)$ and $\operatorname {top}_{J}(\sigma)$ are 1-cells; the pair ij is called the type of the arc σ; the type of an arc captures exactly the upward embedding in the plane of this arc together with its adjacent arcs with the property that the arcs incident to a node σ appear in circular order $\sigma_{\operatorname {r}},\sigma_{\operatorname {f}}, \sigma_{\operatorname {l}}$, and $\sigma_{\operatorname {b}}$ where by convention we ignore $\sigma_{\operatorname {r}}$ or (exclusive) $\sigma_{\operatorname {l}}$ if one of them is not defined, that is, if σ is a right 1-cell or a left 1-cell, as illustrated in Fig. 17. We make the set of cross-sections into a poset $\mathcal{A}(\mathcal {O})$ by defining Γ(J)⪯Γ(J′) in $\mathcal{A}(\mathcal {O})$ by J ⁺⊇J′⁺ where J ⁺ is the filter of cells $z \in \mathcal {O}$ such that x⪯z for some x∈J. The covering relations in $\mathcal{A}(\mathcal {O})$ are described in the following theorem, from which it follows by induction, starting from the obviously acyclic cross-sections of Examples 1.4 and 1.5, that cross-sections are acyclic.

Fig. 17

The nine possible types of a bounded arc of a cross-section whose source and sink are 1-cells

Theorem 2.7

Let J be a maximal antichain of $\mathcal {O}$, let $v \in \mathcal {O}^{0}$, $e,e',f,f' \in \mathcal {O}^{1}$, $\sigma,\sigma' \in \mathcal {O}^{2}$ with $v = \operatorname {sink}(\sigma)= \operatorname {sink}(e) = \operatorname {sink}(e') = \operatorname {sour}(\sigma') = \operatorname {sour}(f) = \operatorname {sour}(f')$. Then v is minimal in the subposet of vertices of J ⁺ if and only if either (first case) σ,e,e′∈J or (second case) v∈J. Furthermore in the first case J′=J−{σ,e,e′}+v is a maximal antichain and Γ(J′) covers Γ(J); in the second case J′=J−v+{f,f′,σ′} is a maximal antichain and Γ(J′) covers Γ(J); and in both case Γ(J′) is obtained from Γ(J) by local changes as indicated in Fig. 18 where the arcs numbered 1,2,3,4 stand for the four 2-cells $v_{\operatorname {r}},v_{\operatorname {f}}, v_{\operatorname {l}}$, and $v_{\operatorname {b}}$ incident to vertex v and where the arcs are oriented upward.

Fig. 18

The covering relations in the poset of cross-sections

Theorem 2.8

Let J be a maximal antichain of $\mathcal {O}$. Then Γ(J) is acyclic (with set of sources $\hat {\mathbf {0}}$ and set of sinks $\hat {\mathbf {1}}$) and can be embedded in free space in such way that the arcs incident to a node σ appear in circular order $\sigma_{\operatorname {r}},\sigma_{\operatorname {f}}, \sigma_{\operatorname {l}}$, and $\sigma_{\operatorname {b}}$ where by convention we ignore $\sigma_{\operatorname {r}}$ or (exclusive) $\sigma_{\operatorname {l}}$ if one of them is not defined, that is, if σ is a right 1-cell or a left 1-cell.

Example 2.6

The Hasse diagram of the poset of cross-sections of the visibility complex of a family of two convex bodies is depicted in Fig. 19: the diagram is of course invariant under the shift operator and its quotient modulo the shift operator is composed of 12 cross-sections.

Fig. 19

The Hasse diagram of the poset of cross-sections of the visibility complex of a family of two bodies: the arcs are oriented upward and the ones incident to a node σ are arranged in the circular order $v_{\operatorname {r}}, v_{\operatorname {f}}, v_{\operatorname {l}}, v_{\operatorname {b}}, \ldots$; the nodes with degree 3 are 1-cells; the nodes with degree 4 are 0-cells, that is, bitangents; the arcs incident to a unique node are the unbounded 2-cells

2.3 ${\mathcal{A} \mathcal{B}}$-Pseudotriangles

The definition of the ${\mathcal{A} \mathcal{B}}$-pseudotriangles is given in terms of the horizon operators φ _α and their dual horizon operators $\varphi _{\alpha _{*}}$ which are defined in exactly the same way except that we replace in the definition of the horizon operators the sink operator by the source operator, i.e., $\varphi _{\alpha _{*}}(\sigma)$ is the source of the 2-cell σ _α ; note that $\varphi _{\operatorname {s}} \varphi _{\alpha _{*}} = \varphi _{\alpha }$. More precisely we are going to use the derived horizon operators $p_{\operatorname {forw}}$ and $p_{\operatorname {back}}$ (and their duals) which are defined as follows:

• (1) $p_{\operatorname {forw}}$ is the operator that assigns to a bitangent line segment v its image under $\overline {\varphi }_{\operatorname {f}}$ if v is a right–left or left–left bitangent line segment whose image under $\overline {\varphi }_{\operatorname {f}}$ is a not a boundary bitangent line segment; the bitangent line segment v otherwise; and

• (2) $p_{\operatorname {back}}$ is the operator that assigns to a bitangent line segment v its image under $\overline {\varphi }_{\operatorname {b}}$ if v is a right–right or left–right bitangent line segment whose image under $\overline {\varphi }_{\operatorname {b}}$ is a not a boundary bitangent line segment; the bitangent line segment v otherwise; note that $p_{\operatorname {back}}$ and $p_{\operatorname {forw}}$ are conjugate under the reorientation operator ι.

As a simple consequence of the description of the greedy pseudotriangulations in terms of the horizon operators given in Theorem 2.6 we see that greedy pseudotriangulations are stable under the operators $p_{\operatorname {forw}}$ and $p_{\operatorname {back}}$.

2.3.1 ${\mathcal{H}}$-Pseudoquadrangles

For σ a bounded 2-cell we set $\operatorname {H}_{\operatorname {rc}}(\sigma) = \operatorname {b}(u)$ if $\operatorname {rc}_{2}(\sigma)$ is reduced to a 0-cell u; otherwise we choose a 1-cell e of $\operatorname {rc}_{2}(\sigma)$, we introduce the sequence $u_{0} = \operatorname {b} \varphi _{\operatorname {b}}(e), u_{i+1} = p_{\operatorname {back}}(u_{i})$, the sequence $v_{0} = \operatorname {b}{ \varphi _{\operatorname {f}}}_{*}(e),v_{i+1} = p_{\operatorname {forw}_{*}}(v_{i})$, and we set

$$ \operatorname {H}_{\operatorname {rc}}(\sigma) = \operatorname {H}^-_{\operatorname {rc}}(\sigma,e) \operatorname {H}^+_{\operatorname {rc}}( \sigma , e) $$

(6)

where $\operatorname {H}^{+}_{\operatorname {rc}}(\sigma, e)$ is, depending on whether u ₀ is a boundary bitangent line segment or not, the empty sequence or the sequence of u _i truncated just after the first index i such that u _i =u _i+1, and where, similarly, $\operatorname {H}^{-}_{\operatorname {rc}}(\sigma, e)$ is, depending on whether v ₀ is a boundary bitangent line segment or not, the empty sequence or the reversal of the sequence of v _i truncated just after the first index i such that v _i =v _i+1. The bitangent line segments corresponding to the vertices of $\operatorname {rc}_{2}(\sigma)$ are consecutive elements of the sequence $\operatorname {H}_{\operatorname {rc}}(\sigma)$, from which it follows that $\operatorname {H}_{\operatorname {rc}}(\sigma)$ is independent of the choice of the 1-cell e. It is convenient to extend the definitions of $\operatorname {H}^{-}_{\operatorname {rc}}(\sigma ,.)$ and $\operatorname {H}^{+}_{\operatorname {rc}}(\sigma,.)$ to the whole set of 1-cells of $\operatorname {rc}(\sigma)$ as follows:

where ϵ is the empty chain, so that (6) holds for any 1-cell e of $\operatorname {rc}(\sigma)$. Let u ₀,u ₁,… be the sequence of bitangent line segments defined by u ₀ is the source bitangent line segment of σ and $u_{i+1} = p_{\operatorname {forw}_{*}}(u_{i})$; similarly, let v ₀,v ₁,… be the sequence of bitangent line segments defined by v ₀ is the sink bitangent line segment of σ and $v_{i+1} = p_{\operatorname {back}}(v_{i})$; clearly by construction one has

$$ \operatorname {H}_{\operatorname {rc}}(\sigma) = \operatorname {H}^1_{\operatorname {rc}}(\sigma) \operatorname {H}^2_{\operatorname {rc}}(\sigma) \operatorname {H}^3_{\operatorname {rc}}(\sigma) $$

(7)

where (1) $\operatorname {H}^{1}_{\operatorname {rc}}(\sigma)$ is the empty sequence if u ₁ is a boundary bitangent line segment or if u ₀=u ₁; the reversal of the sequence u ₁,u ₂,… , truncated just after the first index i such that u _i =u _i+1, otherwise; (2) $\operatorname {H}^{2}_{\operatorname {rc}}(\sigma)$ is the sequence of bitangent line segments corresponding to the sequence of vertices of the chain $\operatorname {rc}_{2}(\sigma)$; and (3) $\operatorname {H}^{3}_{\operatorname {rc}}(\sigma)$ is the empty sequence if v ₁ is a boundary bitangent line segment or if v ₀=v ₁; the sequence v ₁,v ₂,… , truncated just after the first index such that v _i =v _i+1, otherwise. We consider $\operatorname {H}_{\operatorname {rc}}$ as an operator on the set of bounded 2-cells and we define $\operatorname {H}_{\operatorname {lc}}$ to be its conjugate under ι.

Example 2.7

The table of the operators $\operatorname {H}_{\operatorname {rc}}^{i}$ on the 2-cells of the visibility complex of two convex bodies of the plane is the following:

$$\begin{array}{l@{\quad}l@{\quad}l@{\quad}l@{\quad}l@{\quad}l@{\quad}l} \hline \sigma& \operatorname {H}^1_{\operatorname {rc}}(\sigma) & \operatorname {H}^2_{\operatorname {rc}}(\sigma) & \operatorname {H}^3_{\operatorname {rc}}(\sigma) & \operatorname {H}^1_{\operatorname {lc}}(\sigma) & \operatorname {H}^2_{\operatorname {lc}}(\sigma ) & \operatorname {H}^3_{\operatorname {lc}}(\sigma) \\ \hline ij & \epsilon& 3'& \epsilon & \epsilon& 2& \epsilon\\ ji & \epsilon& 2'& \epsilon& \epsilon& 3& \epsilon\\ i\infty& \epsilon& 4'&\epsilon& \epsilon& 1& \epsilon \\ \infty i& \epsilon& 1'&\epsilon& \epsilon & 4&\epsilon \\ j\infty&\epsilon& 4& \epsilon&\epsilon & 1'& \epsilon \\ \infty j &\epsilon& 1& \epsilon&\epsilon & 4'& \epsilon \\ \infty\infty& \epsilon& \epsilon& \epsilon& \epsilon& \epsilon& \epsilon\\ \infty\infty& \epsilon& \epsilon& \epsilon& \epsilon& \epsilon& \epsilon\\ \hline \end{array} $$

where we use the notations of Fig. 14 and where ϵ stands for the empty sequence.

Example 2.8

Consider the family of seven convex bodies o ₁,o ₂,o ₃,…,o ₇ of the real affine plane depicted in the left part of Fig. 20 and let σ be the 2-cell of its visibility complex that contains the directed line segment labeled σ. Then, using the notations $b_{ij}, b_{\overline{i}j}, b_{i\overline{j}}, b_{\overline{ij}}$ for the left–left, right–left, left–right, right–right bitangent line segments joining o _i to o _j , its source and sink bitangent line segments are the line segments b ₂₆ and $b_{\overline{4}3}$ and the $\operatorname {H}_{\operatorname {rc}}^{i}(\sigma)$ and $\operatorname {H}_{\operatorname {lc}}^{i}(\sigma)$ are given in Table 3.

Fig. 20

Refers to Example 2.8

Table 3 Refers to Example 2.8

Observe, as illustrated in the right part of the figure, that the bitangent line segments of $\operatorname {H}_{\operatorname {rc}}(\sigma)$ and $\operatorname {H}_{\operatorname {lc}}(\sigma )$ are the bitangent line segments of a pseudoquadrangle with diagonals the source and sink bitangent line segments of σ.

Example 2.9

Consider the family of seven convex bodies o ₁,o ₂,…,o ₇ of the real affine plane depicted in Fig. 21 and let σ be the 2-cell of its visibility complex that contains the directed line segment labeled σ. Then its source and sink bitangent line segments are the boundary bitangent line segments b ₂₁ and $b_{\overline{7}\overline{1}}$ and the $\operatorname {H}_{\operatorname {rc}}^{i}(\sigma)$ and $\operatorname {H}_{\operatorname {lc}}^{i}(\sigma)$ are given in Table 4. Observe that the bitangent line segments of $\operatorname {H}_{\operatorname {rc}}(\sigma )/\operatorname {H}_{\operatorname {lc}}(\sigma)$ augmented with the sink/source of σ bound a pseudotriangle.

Fig. 21

Refers to Example 2.9

Table 4 Refers to Example 2.9

We now reinterpret the sequence $\operatorname {H}_{\operatorname {rc}}(\sigma)$ and $\operatorname {H}_{\operatorname {lc}}(\sigma)$ through the greedy pseudotriangulations. Let σ be a bounded 2-cell, let e be the last 1-cell of $\operatorname {lc}_{1}(\sigma)$ if any, the first 1-cell of $\operatorname {lc}_{2}(\sigma)$ otherwise, let a be the initial point of $\operatorname {b}\circ\ \operatorname {sink}(e)$ or $\operatorname {b}\circ\ \operatorname {sour}(e)$ depending on whether e is the last 1-cell of $\operatorname {lc}_{1}(\sigma)$ or the first 1-cell of $\operatorname {lc}_{2}(\sigma)$, and let J be the maximal antichain whose 1-, and bounded 2-cells are the cells whose sinks are in the principal filter of the sink of e but not their sources. We define inductively a finite sequence of pseudotriangulations G ₁,G ₂,…,G _p , and a finite sequence of pseudotriangles Δ ₁,Δ ₂,…,Δ _p , a∈∂Δ _i , as follows:

• (1) $G_{1} = \operatorname {b}\circ \operatorname {G}(J)$ and Δ ₁ is the pseudotriangle of G ₁ lying locally to the left of the sink bitangent line segment of σ if any; otherwise (that is, if the sink bitangent line segment of σ is a right–right boundary bitangent line segment as in the example of Fig. 21) we define Δ ₁ to be the pseudotriangle lying locally to the right of the image under ι of the source bitangent line segment of σ; walking in counterclockwise order along the boundary of a pseudotriangle Δ _i , a∈∂Δ _i , starting from the point a we traverse successively four convex chains $\varDelta^{1}_{i}, \varDelta^{2}_{i}, \varDelta^{3}_{i}$ and $\varDelta^{4}_{i}$, the last one $\varDelta^{4}_{i}$ being the empty chain in case a is a cusp point of Δ _i ;

• (2) If $\varDelta_{i}^{3}$ is an arc or a boundary bitangent line segment we set i=p and we are done; otherwise we define Δ _i+1 to be the pseudotriangle lying locally to the left of the sink bitangent line segment of σ in the pseudotriangulation G _i+1 obtained by flipping clockwise in G _i the first bitangent line segment t _i of $\varDelta_{i}^{3}$.

Playing the same game with e′ the last 1-cell of $\operatorname {rc}_{1}(\sigma )$ if any, the first 1-cell of $\operatorname {rc}_{2}(\sigma)$ otherwise, we define similarly a sequence of pseudotriangulations $G'_{1},\ldots, G'_{p'}$ and a sequence of pseudotriangles $\varDelta'_{1},\ldots, \varDelta'_{p'}$. We denote by $\operatorname {L}_{\operatorname {sink}}$ and $\operatorname {R}_{\operatorname {sink}}$ the operators that assign to a bounded 2-cell σ the pseudotriangle Δ _p and $\varDelta'_{p'}$ defined above; note that $\operatorname {R}_{\operatorname {sink}}$ and $\operatorname {L}_{\operatorname {sink}}$ are conjugate under ι. Finally playing the same game with the dual order of the order ≺ we introduce similarly the operators $\operatorname {L}_{\operatorname {sour}}$ and $\operatorname {R}_{\operatorname {sour}}$.

Example 2.10

Figure 22 depicts the sequences of pseudotriangulations $G_{i}, G'_{i}$ together with the pseudotriangles $\varDelta_{i}, \varDelta'_{i}$ for the 2-cell σ of the visibility complex of the family of bodies introduced in Example 2.9: A case where the sink of σ is a right–right boundary bitangent: Here e is the first 1-cell of $\operatorname {lc}_{2}(\sigma)$ and its sink is b ₂₃; e′ is the last 1-cell of $\operatorname {rc}_{1}(\sigma)$ and its sink is $b_{\overline{6}1}$, p=p′=1.

Fig. 22

Refers to Example 2.10

Example 2.11

Figure 23 depicts the sequences of pseudotriangulations $G_{i}, G'_{i}$ together with the pseudotriangles $\varDelta_{i}, \varDelta'_{i}$ for the 2-cell σ of the visibility complex of the family of bodies introduced in Example 2.8: here e is the first 1-cell of $\operatorname {lc}_{2}(\sigma)$, the sink of e is the bitangent b ₂₃, p=4, the sequence t ₁,t ₂,t ₃ of flipped bitangents is the sequence $b_{1\overline {2}}, b_{17}, b_{1\overline{7}}$, e′ is the last 1-cell of $\operatorname {rc}_{1}(\sigma)$, the sink of e′ is the bitangent $b_{\overline{5}6}$ and p′=1.

Fig. 23

Refers to Example 2.11

Theorem 2.9

Let σ be a bounded 2-cell whose source is an interior vertex. Then the pseudotriangles $\operatorname {L}_{\operatorname {sink}}(\sigma)$ and $\operatorname {R}_{\operatorname {sink}}(\sigma)$ are adjacent along $\operatorname {sink}(\sigma)$ and their union $\operatorname {\mathcal {H}}(\sigma)$ is a free pseudoquadrangle whose bitangent line segments lying on its boundary are the bitangent line segments of $\operatorname {H}_{\operatorname {rc}}(\sigma)$ and $\operatorname {H}_{\operatorname {lc}}(\sigma)$, possibly augmented with one or two boundary bitangent line segments in case the first or the last or both the first and the last elements of the label of σ are the infinity symbol. Similarly the pseudotriangles $\operatorname {L}_{\operatorname {sour}}(\sigma)$ and $\operatorname {R}_{\operatorname {sour}}(\sigma )$ are adjacent along $\operatorname {sour}(\sigma)$ and their union is $\operatorname {\mathcal {H}}(\sigma)$.

Proof

We denote by $\nabla _{i}^{j}$ the sequence of bitangent line segments of the chain $\varDelta_{i}^{j}$, j∈{1,2,3,4}, i=1,2,…,p. One can easily check that the sequence Δ _i is well-defined, finite, and that

• (1) $\varDelta_{1}^{1} = \varDelta_{2}^{1}= \cdots= \varDelta_{p}^{1}$, $\nabla _{1}^{1} =\operatorname {H}^{2}_{\operatorname {lc}}(\sigma)$, and $\nabla _{p}^{4} = \operatorname {H}^{1}_{\operatorname {lc}}(\sigma)$;

• (2) $\varDelta_{i}^{2}$ is a prefix factor of $\varDelta_{i+1}^{2}$, and $\nabla _{p}^{2} = \operatorname {sink}(\sigma)\operatorname {H}^{3}_{\operatorname {rc}}(\sigma)$ unless the sink bitangent of σ is a right–right boundary bitangent, in which case $\varDelta_{p}^{2} = \varDelta_{1}^{2}$ is an arc.

The theorem follows. □

Theorem 2.10

Let σ be bounded 2-cell whose source is a boundary vertex. Then the bitangent line segments of the sequence $\operatorname {H}_{\operatorname {rc}}(\sigma)$ (resp. $\operatorname {H}_{\operatorname {lc}}(\sigma)$) bound a pseudotriangle incident to the boundary of the convex hull along the bitangent line segment corresponding to the sink (resp. source) or the source (resp. sink) of σ depending on whether the source of σ is a left–left or a right–right bitangent.

Note that under the assumption that the source of σ is a boundary bitangent then the pseudotriangle defined by $\operatorname {H}_{\operatorname {rc}}(\sigma)$ is denoted indifferently $\operatorname {R}_{\operatorname {sink}}(\sigma)$ or $\operatorname {R}_{\operatorname {sour}}(\sigma)$; similarly the pseudotriangle defined by $\operatorname {H}_{\operatorname {lc}}(\sigma)$ is denoted indifferently $\operatorname {L}_{\operatorname {sink}}(\sigma)$ or $\operatorname {L}_{\operatorname {sour}}(\sigma)$.

Combining now Theorem 2.6 and the previous analysis we get the following key result for our purpose.

Theorem 2.11

Let σ be bounded 2-cell and let e be a left 1-cell of the left boundary chain of σ. Then the bitangent $\varphi _{\operatorname {b}}(e)$ leaves the pseudotriangle $\operatorname {L}_{\operatorname {sink}}(\sigma)$. (In case the source of σ is a left–left boundary bitangent and if e is the first left 1-cell of the left boundary of σ then $\varphi _{\operatorname {b}}(e)$ and the image under ι of the source of σ coincide.)

2.3.2 ${\mathcal{A}\mathcal{B}_{0}}$-Pseudotriangles

Let J be a maximal antichain of $\mathcal {O}$ free of vertices. We use the symbols $\operatorname {ur}_{J},\operatorname {ul}_{J},\allowbreak \operatorname {dr}_{J},\operatorname {dl}_{J}$ for the products $\operatorname {urf}\circ \operatorname {top}_{J}$, $\operatorname {ulf}\circ \operatorname {top}_{J}$, $\operatorname {drf}\circ \operatorname {bot}_{J}$, $\operatorname {dlf}\circ \operatorname {bot}_{J}$ where $\operatorname {urf}(\sigma) = \sigma _{\operatorname {f}}$ ($\operatorname {urf}$ for “upper right face”), $\operatorname {ulf}(\sigma) = \sigma _{\operatorname {b}}$, $\operatorname {drf}(\sigma) = \operatorname {dlf}(\sigma) = \sigma _{\operatorname {r}}$ for a left–left 0-cell or a left 1-cell σ, and where $\operatorname {urf}(\sigma) = \operatorname {ulf}(\sigma) = \sigma _{\operatorname {l}}$, $\operatorname {drf}(\sigma) = \sigma _{\operatorname {b}}$, $\operatorname {dlf}(\sigma) = \sigma _{\operatorname {f}}$ for a right–right 0-cell or a right 1-cell σ. (Note that $\operatorname {urf}$ and $\operatorname {dlf}$ on one hand and $\operatorname {ulf}$ and $\operatorname {drf}$ on the other hand are conjugate under ν.) The ${\mathcal{A}\mathcal{B}_{0}}$-pseudotriangles of σ, $\sigma\in \mathcal {F}^{\circ }(J)$, are denoted and and are defined as follows:

(8)

and

(9)

where, recall, $\mathcal {F}_{ij}(J)$, i,j∈{1,2,3}, denotes the set of $\sigma\in \mathcal {F}(J)$ such that $\operatorname {bot}_{J}(\sigma) \in \operatorname {rc}_{i}(\sigma)$ and $\operatorname {top}_{J}(\sigma ) \in \operatorname {lc}_{j}(\sigma)$; cf. Theorem 2.3. (For J,K subsets of {1,2,3} we set $\mathcal {F}_{JK} (J)= \bigcup_{i \in J, j\in K} \mathcal {F}_{ij} (J)$.) Note that the operators and are conjugate under ι.

Theorem 2.12

Let J be a maximal antichain of $\mathcal {O}$ free of vertices and let $\sigma\in \mathcal {F}^{\circ }(J)$ whose source is a left–left (resp. right–right) boundary vertex. Then its sink bitangent line segment is a right–right (resp. left–left) bitangent line segment and is one of the three sides of (resp. ).

Theorem 2.13

Let J be a maximal antichain of $\mathcal {O}$ free of vertices and let $\sigma\in \mathcal {F}^{\circ }(J)$ whose source is an interior vertex. Then the source bitangent line segment of σ belongs to the boundary of , the pseudotriangle lies locally on the left side of the source bitangent of σ, and the sink bitangent line segment of σ leaves .

Proof

Assume first that $\sigma\in \mathcal {F}_{\{2,3\}\{1,2,3\}}(J)$. Then and we conclude using the definition of $\operatorname {R}_{\operatorname {sour}}(\sigma)$ and Theorem 2.10. Assume now that $\sigma\in \mathcal {F}_{1\{1,2,3\}}(J)$. Then one can easily check that

• (1) $\operatorname {dl}_{J}(\sigma) \notin \hat {\mathbf {0}}$;

• (2) $\operatorname {bot}_{J}(\sigma)$ is a left 1-cell of the left boundary of $\operatorname {dl}_{J}(\sigma)$;

• (3) $\operatorname {sour}(\sigma) = \varphi _{\operatorname {b}_{*}}(\operatorname {bot}_{J}(\sigma))$ and $\operatorname {sink}(\sigma)= \varphi _{\operatorname {b}}(\operatorname {bot}_{J}(\sigma))$;

• (4) $\operatorname {b}\circ \operatorname {sour}(\sigma)\in \operatorname {H}^{+}_{\operatorname {lc}}(\operatorname {dl}_{J}(\sigma),\operatorname {bot}_{J}(\sigma))$ (since $\operatorname {sour}(\sigma)$ is an interior vertex);

• (5) ;

from which it follows that the source bitangent line segment of σ appears in the boundary of . It remains to prove that $\operatorname {sink}(\sigma)$ leaves ; but this is exactly the statement of Theorem 2.11. □

Thanks to the conjugation relation we see that and are adjacent along the source bitangent line segment of σ and that the sink bitangent line segment of σ joins to . Walking in counterclockwise order around the boundary of starting from the tail of the source bitangent line segment of σ we find successively the convex chains , , (which is reduced to an arc or a boundary bitangent line segment), and . Let be the concatenation of the chains and . We know that the sink bitangent line segment of σ leaves the chain , that $\operatorname {b}(\operatorname {bot}_{J}(\sigma))$ is a subarc of an arc, say τ ⁻, of the chain : so we define to be the suffix subchain of starting at τ ⁻. Similarly we define the chain . By construction the sink bitangent line segment of σ leaves the chain and reaches the chain ; however, one cannot use directly these chains to compute the sink bitangent of σ because neither the source of the first arc of nor the sink of its last arc are efficiently computable.

2.3.3 ${\mathcal{A} \mathcal{B}}$-Pseudotriangles

We now assume that the convex bodies of ${\mathcal{D}}$ are lifts of convex bodies of a finite family $\overline {{\mathcal{D}}}$ of pairwise disjoint convex bodies of the topological plane $\mathbb {A}$. The central point of a convex body of ${\mathcal{D}}$ is defined to be the branched point contained in that body if any; otherwise any point chosen arbitrarily in its interior. A boundary tangent is a tangent to the convex hull of convex bodies of ${\mathcal{D}}$; all other tangents are said to be interior tangents. The backward/forward view of a line is the first/last atom of its label.

Let s be the initial segment of an interior tangent t to a convex body o of ${\mathcal{D}}$ with backward view a convex body o′. We set ${\mathcal{D}}(s) = \{\overline{o},\overline{o}'\} \subseteq \overline {{\mathcal{D}}}$. Let γ be a simple oriented curve in o′∪o∪s joining the central point of o′ to the central point of o with the property that its projection γ′ in $\mathbb {A}$ is simple, as illustrated in the left top and left bottom diagrams of Fig. 24. We construct a new branched covering $\lambda ^{}_{s}{(\mathbb {B}_{})}$ of $\mathbb {A}$ as follows. We cut $\mathbb{C} = \mathbb {B}_{} \sqcup \mathbb {A}$ along γ and γ′, call ℂ _γ the resulting surface and q:ℂ _γ →ℂ the induced projection; we define $\lambda ^{}_{s}{(\mathbb {B}_{})}$ as the quotient space of ℂ _γ by identifying, on one hand, the left lift (under q) of γ and the right lift of γ′ and, on the other hand, the right lift of γ and the left lift of γ′. By construction the set $\lambda ^{}_{s}({\mathcal{D}})$ of connected components of $q^{-1}(\bigcup({\mathcal{D}}\cup {\mathcal{D}}(s)))$ is a set of pairwise disjoint convex bodies of $\lambda ^{}_{s}(\mathbb {B}_{})$. A similar construction can be done with the terminal segment of the interior tangent in place of its initial segment.

Fig. 24

Illustrates the definition of the ${\mathcal{A} \mathcal{B}}$-pseudotriangles

Theorem 2.14

Let s be the initial segment of an interior tangent to a convex body o of ${\mathcal{D}}$ with backward view a convex body o′, let $\sigma= \operatorname {dlf}(s)$ and let $\sigma' = \operatorname {dlf}(s')$ where s′ is the right lift of s in the visibility complex of $\lambda ^{}_{s}({\mathcal{D}})$. Then $\operatorname {sink}(\sigma') = \operatorname {sink}(\sigma)$, $\operatorname {H}_{\operatorname {rc}}(\sigma') = \operatorname {H}_{\operatorname {rc}}(\sigma)$, $\operatorname {H}^{+}_{\operatorname {lc}}(\sigma',s') = \operatorname {H}^{+}_{\operatorname {lc}}(\sigma,s)$, and $\operatorname {H}^{-}_{\operatorname {lc}}(\sigma', s')$ is the right–left or right–right bitangent line segment joining $\overline{o}'$ to $\overline{o}$ depending on whether s is a left or right tangent. A similar result holds for the terminal segment of an interior tangent with forward view a convex body.

Proof

By construction modulo the simple observation that the segment s does not cross any of the bitangent line segments of $\operatorname {H}_{\operatorname {rc}}(\sigma)$ and $\operatorname {H}_{\operatorname {lc}}(\sigma)$. □

A similar construction is done in the case where the backward view of t is the infinity symbol using the left–left boundary bitangent line segment v pierced by s and the convex body o′ that v leaves, as illustrated in the right diagrams of Fig. 24. Note that in the case where t is a left tangent one can have o=o′.

Theorem 2.15

Let s be the initial segment of an interior tangent whose backward view is the infinity symbol, let $\sigma= \operatorname {dlf}(s)$ and let $\sigma' = \operatorname {dlf}(s')$ where s′ is the right lift of s in the visibility complex of $\lambda ^{}_{s}({\mathcal{D}})$. Then $\operatorname {sink}(\sigma') = \operatorname {sink}(\sigma)$, $\operatorname {H}_{\operatorname {rc}}(\sigma') = \operatorname {H}_{\operatorname {rc}}(\sigma)$, $\operatorname {H}^{+}_{\operatorname {lc}}(\sigma',s') = \operatorname {H}^{+}_{\operatorname {lc}}(\sigma,s)$, and $\operatorname {H}^{-}_{\operatorname {lc}}(\sigma', s')$ is the left–right bitangent line segment joining $\overline{o}'$ to $\overline{o}$ if s is a right tangent, the left–left bitangent line segment joining $\overline{o}'$ to $\overline{o}$ if s is a left tangent and o≠o′; the empty sequence otherwise. A similar result holds for the terminal segment of an interior tangent whose forward view is the infinity symbol.

We turn now to the definition of the ${\mathcal{A} \mathcal{B}}$-pseudotriangles.

Let J be a maximal antichain free of vertices of $\mathcal {O}({\mathcal{D}})$ with a distinguished line τ(e)∈e for each $e \in \mathcal {E}(J)$ and let s be the initial segment of one of the τ(e), $e \in \mathcal {E}(J)$, with the property that the supporting line of s is an interior tangent. Let J′ be a maximal antichain free of vertices of $\mathcal {O}({\mathcal{D}}(s))$ with a distinguished line τ(e)∈e for each $e \in \mathcal {E}(J')$ such that J and J′ agree along the supporting line t of s, that is, the projection of t in $\mathbb {A}$ is a τ(e′) for some $e'\in \mathcal {E}(J')$. In that case the lines q ⁻¹(τ(e)), $e \in \mathcal {E}(J) \sqcup \mathcal {E}(J')$, define a maximal antichain of the visibility complex of $\lambda ^{}_{s}({\mathcal{D}})$, denoted $\lambda ^{}_{s}(J)$ thereafter.

Let $\sigma\in \mathcal {F}_{xy}(J)$ whose source is an interior vertex. We define $\mu ^{+}(\mathbb {B}_{})$, $\mu ^{+}({\mathcal{D}})$, μ ⁺(J), and μ ⁺(σ) to be $\lambda ^{}_{s}(\mathbb {B}_{})$, $\lambda ^{}_{s}({\mathcal{D}})$, $\lambda ^{}_{s}(J)$, and $\operatorname {dlf}(s')$, where s is the initial segment of $\tau (\operatorname {top}_{J}(\sigma))$ and s′ is the right lift in $\mu ^{+}(\mathbb {B}_{})$ of s, if y∈{2,3}; $\mathbb {B}_{}$, ${\mathcal{D}}$, J, and σ otherwise. We define μ ⁻ to be the conjugate of μ ⁺ under ι and we set μ=μ ⁻∘μ ⁺. Applying twice Theorem 2.14 we get the following theorem where we write $\operatorname {H}^{+}_{\operatorname {rc}}(\sigma; J)$, $\operatorname {H}^{+}_{\operatorname {lc}}(\sigma; J)$, $\operatorname {H}^{-}_{\operatorname {rc}}(\sigma; J)$, $\operatorname {H}^{-}_{\operatorname {lc}}(\sigma; J)$, for $\operatorname {H}^{+}_{\operatorname {rc}}(\sigma, \operatorname {bot}_{J}(\sigma))$, $\operatorname {H}^{+}_{\operatorname {lc}}(\sigma, \operatorname {top}_{J}(\sigma))$, $\operatorname {H}^{-}_{\operatorname {rc}}(\sigma, \operatorname {bot}_{J}(\sigma))$, and $\operatorname {H}^{-}_{\operatorname {lc}}(\sigma, \operatorname {top}_{J}(\sigma))$.

Theorem 2.16

Let $\sigma\in \mathcal {F}_{xy}(J)$ whose source is an interior vertex, let J′=μ(J), and let σ′=μ(σ). Then

• (1) $\sigma'\in \mathcal {F}_{xy}(J')$;

• (2) $\operatorname {sink}(\sigma) = \operatorname {sink}(\sigma')$;

• (3) $\operatorname {H}^{+}_{\operatorname {rc}}(\sigma'; J') = \operatorname {H}^{+}_{\operatorname {rc}}(\sigma;J)$, $\operatorname {H}^{+}_{\operatorname {lc}}(\sigma';J') = \operatorname {H}^{+}_{\operatorname {lc}}(\sigma;J)$; and

• (4) $\operatorname {H}^{-}_{\operatorname {rc}}(\sigma';J')$, $\operatorname {H}^{-}_{\operatorname {lc}}(\sigma'; J')$, and $\operatorname {sour}(\sigma')$ are computable in constant time.

As announced in the introduction the ${\mathcal{A} \mathcal{B}}$-pseudotriangles of σ are the ${\mathcal{A}\mathcal{B}_{0}}$-pseudotriangles of μ(σ); they are denoted and in the sequel.

2.3.4 Summary

We reformulate, in preparation to the description of our pseudotriangulation algorithm in the next section, Theorem 2.16 using the following more adequate notations. For $\sigma\in \mathcal {F}^{\circ }(J)$ we set

$$ \mathcal {K}_{\operatorname {dl}}(\sigma) = \begin{cases} \emptyset& \text{if $\sigma\in \mathcal {F}_{3\{1,2,3\}}(J)$;}\\ \{\operatorname {dl}_{J}(\sigma)\} & \text{if $\sigma\in \mathcal {F}_{2\{1,2,3\}}(J)$}; \\ \{\operatorname {dl}_{J}(\sigma), \operatorname {ur}_{J} \circ \operatorname {dl}_{J}(\sigma)\} & \text {otherwise;} \end{cases} $$

(10)

similarly we define $\mathcal {K}_{\operatorname {ur}}(\sigma)$ to be the empty set if $\sigma\in \mathcal {F}_{\{1,2,3\}3}(J)$; the singleton $\{\operatorname {ur}_{J}(\sigma )\}$ if $\sigma\in \mathcal {F}_{\{1,2,3\}2}(J)$; the pair $\{\operatorname {ur}_{J}(\sigma), \operatorname {dl}_{J} \circ \operatorname {ur}_{J}(\sigma)\}$ otherwise; note that $\mathcal {K}_{\operatorname {ur}}$ is the conjugate of $\mathcal {K}_{\operatorname {dl}}$ under the shift operator ν. Thus Theorem 2.16 can be read as follows.

Theorem 2.17

Assume that the orbits of the sink bitangent line segments of the 2-cells of $\mathcal {K}_{\operatorname {dl}}(\sigma) \cup \mathcal {K}_{\operatorname {ur}}(\sigma)$ under the operators $p_{\operatorname {back}}$ and $p_{\operatorname {forw}}$ are known. Then representations of the ${\mathcal{A} \mathcal{B}}$-pseudotriangles and are computable in constant time.

Let G be the digraph whose set of nodes is the set of arcs of the cross-section and whose set of arcs is the set of pairs (σ,σ′), $\sigma'\in \mathcal {K}_{\operatorname {dl}}(\sigma) \cup \mathcal {K}_{\operatorname {ur}}(\sigma)$, as illustrated in Fig. 25 where we have drawn G on the canonical upward drawing of the cross-section. If G is acyclic then, according to Theorem 2.17, any topological sort of G provides a total order on the set of arcs of the cross-section to compute their ${\mathcal{A} \mathcal{B}}$-pseudotriangles in constant time per arc. Unfortunately the digraph G is not acyclic in general. The following (easy to check) theorem will be used in the next section to decide where to break the cycles of G in order to be able to compute the ${\mathcal{A} \mathcal{B}}$-pseudotriangles no longer in constant time but in constant amortized time per arc.

Fig. 25

Illustrates the definition of the digraph G

Theorem 2.18

Let σ be a left 1-cell of J. Then $\operatorname {urf}(\sigma) \in \mathcal {F}_{3\{1,2,3\}}(J)$, $\operatorname {ulf}(\sigma) \in \mathcal {F}_{1\{1,2,3\}}(J)$, and $\operatorname {drf}(\sigma) = \operatorname {dlf}(\sigma) \in \mathcal {F}_{\{1,2,3\}2}(J) \cup \hat {\mathbf {0}}$. A similar result holds for right 1-cell of J using the conjugation relation $\mathcal {F}_{ij} \circ \iota = \iota \circ \mathcal {F}_{ji}$.

3 Our Algorithm and Its Complexity Analysis

We are now ready to describe our pseudotriangulation algorithm. Recall that our pseudotriangulation algorithm proceeds in three steps: we first compute the convex hull of the family of convex bodies, then the cross-section of the visibility complex of the family of convex bodies with constraints assigned to a boundary bitangent line segment (not forgetting to add all the boundary bitangent line segments computed at the first step to the set of constraints), and finally the greedy pseudotriangulation associated with that cross-section. The input of our pseudotriangulation algorithm is a finite planar family of pairwise disjoint convex bodies together with a distinguished set of pairwise interior non-crossing free bitangent line segments of the family: the constraints; the family is only given by its chirotope, that is, for all triple of indices of the family the position vector of the corresponding triple of convex bodies is computable in constant time; equivalently, for any convex body of the family the relative counterclockwise circular order of any triple of bitangents tangent to that body is computable in constant time; cf. Appendix A. The family is denoted ${\mathcal{D}}= \{o_{0},o_{1},\ldots,o_{n-1}\}$, the underlying topological plane is denoted $\mathbb {A}$, and the left–left, left–right, right–left and right–right bitangent line segments joining the body o _i to the body o _j are denoted v _ij , $v_{i\overline{j}}$, $v_{\overline{i}j}$ and $v_{\overline{ij}}$, respectively.

3.1 Convex Hull Algorithm

Let $p : \mathbb {B}_{} \rightarrow \mathbb {A}$ be a (connected) 4-sheeted branched covering of $\mathbb {A}$ ramified over the central point of o ₀, let τ be a generator of its automorphism group (≈ℤ₄), and let X _i , i∈ℤ₄, τ(X _i )=X _i+1, be the four connected components of the pre-image under $\mathbb {B}_{} \rightarrow \mathbb {A}$ of the complement in $\mathbb {A}$ of a curve γ⊂o ₀∪v ₀₁ joining the central point of o ₀ to the point at +∞ on the bitangent v ₀₁. The sole lift c of o ₀ is called the central body, and the lift of o _i , i≠0, whose interior is entirely included in X _k , k∈ℤ₄, or intersects both X _k and X _k+1 is denoted o _i (k). We denote by $\widehat {{\mathcal{D}}}$ the family of o _i (k), k∈{0,1,2}, augmented with the central body. Our algorithm to compute the bitangent line segments of the convex hull of ${\mathcal{D}}$ is based on the following three simple observations.

• (1) The set of bitangent line segments of the family $\widehat {{\mathcal{D}}}$ and the set of pairs of crossing bitangent line segments of the family $\widehat {{\mathcal{D}}}$ depend only on the chirotope of the family ${\mathcal{D}}$;

• (2) The convex hull of the family ${\mathcal{D}}$ can be extracted in linear time from the convex hull of the family $\widehat {{\mathcal{D}}}$; indeed, let Σ be the counterclockwise linear sequence of bitangent line segments that appear in the boundary of the convex hull of the family $\widehat {{\mathcal{D}}}$ starting from the left–left bitangent line segment joining the central body to o ₁(0), one can easily check (details are left to the reader) that the first bitangent line segment v of Σ entering an o _i (1) is well-defined, that τ(v) appears in the sequence Σ, and that the projection of the factor v…w of Σ where w is the bitangent line segment that precedes τ(v) in Σ is the sequence of bitangent line segments that appear in the boundary of the convex hull of ${\mathcal{D}}$. For example in the configuration depicted in Fig. 26 one has Σ=Σ ₁ vΣ ₂ wτ(v)Σ ₃ with v=v _51′, wτ(v)=v _4′5′ v _5′1″, Σ ₁=v ₀₁ v ₁₂ v ₂₃ v ₃₄ v ₄₅, Σ ₂=v _1′6 v _62′ v _2′3′ v _3′4′, and Σ ₃=v _1″6′ v _6′2″ v _2″3″ v _3″4″ v _4″5″ v _5″6″ v _6″0. The projection of the factor vΣ ₂ w is the counterclockwise sequence of boundary bitangent line segments;

  Fig. 26

  

  The convex hull of the family ${\mathcal{D}}$ is extracted from the convex hull of the family $\widehat {{\mathcal{D}}}$

• (3) Graham’s scan to compute the convex hull of a family of points can be generalized to families of pairwise disjoint convex bodies provided that the bodies are sorted around a boundary body. Since the central body is, by construction, a boundary body of the family $\widehat {{\mathcal{D}}}$ we can apply the generalization of Graham’s scan we have in mind to compute the convex hull of the family $\widehat {{\mathcal{D}}}$, and apply our second observation to derive the convex hull of the family ${\mathcal{D}}$.

We now explain our generalization of the Graham’s scan.

We perform a counterclockwise rotational sweep of the 4-sheeted branched covering space $\mathbb {B}_{}$ with a half-line whose supporting line is a left tangent to the central body c at its origin. The lift in sheet X _k , k∈ℤ₄, of the half-line supporting the bitangent line segment v _oi with origin its tangency point upon o ₀ is denoted ℓ _i (k). The sweep starts at position ℓ ₁(0) and ends at position ℓ ₁(3). During the sweep we maintain the convex hull of the subset of bodies of $\widehat {{\mathcal{D}}}$ that have been entirely or partially swept by the sweeping half-line; to this end we keep track of a subset of the bodies that intersect ℓ; therefore we update our data structures (to be defined in a second) when the sweeping half-line reaches the ℓ _i (k): an enter event, and some of the $\ell_{\overline{i}}(k)$: a leave event. For a given position ℓ of the sweep half-line, we define

• (1) Σ(ℓ) to be the linear sequence v ₁ v ₂…v _k of bitangent line segments encountered when walking counterclockwise along the boundary of the convex hull of the bodies that has been reached so far by the sweep half-line, starting from the left–left bitangent line segment joining the central body to o ₁(0); the body that the bitangent line segment v _i reaches is denoted $o'_{i}$ (in particular $o'_{k}$ is the central body);

• (2) $\operatorname {v}_{*}(\ell)$ to be the bitangent line segment v _j′ where j′ is the minimal element of the subset of indices j (1≤j≤k) such that an infinitesimal counterclockwise shift of ℓ pierces the bodies $o'_{i}$ (j≤i≤k) in the order $o'_{k}, o'_{k-1},\ldots, o'_{j}$; by construction ℓ pierces either $\operatorname {v}_{*}(\ell)$, or its successor arc or its successor bitangent line segment;

• (3) $\operatorname {Q}(\ell)$ to be the list of bodies $o'_{k} o'_{k-1}\ldots o'_{j'}$.

For example in the configuration depicted in Fig. 27 the set of convex bodies entirely or partially swept by the current sweeping half-line ℓ is {0,1,2,3,4,5,6,1′} and one has

Fig. 27

Illustrates our generalization of the Graham’s scan

During the sweep, we maintain the lists Σ(ℓ), $\operatorname {Q}(\ell)$, and the bitangent line segment $\operatorname {v}_{*}(\ell)$. Initially ℓ=ℓ ₁(0), $\operatorname {v}_{*}(\ell)$ is the left–left bitangent line segment $v_{c, o_{1}(0)}$ joining the central body to o ₁(0), $\varSigma (\ell) = [v_{c, o_{1}(0)}, v_{o_{1}(0),c}]$, and $\operatorname {Q}(\ell) = [c, o_{1}(0)]$. We store $\operatorname {Q}(\ell)$ in a binary search tree. Assume we are to process the enter-event ℓ′ for the body o successor of the enter or leave event ℓ. Let r be the rightmost body of $\operatorname {Q}(\ell )$, r _∗ its predecessor along Σ(ℓ), and r ^∗ its successor, if any, that is, if r is not the central body. Now, we explain how to update Σ and $\operatorname {Q}$. First we locate o in $\operatorname {Q}$. Assume first that o is to the left of r. Let α and α′ be its left-hand and right-hand neighbors in $\operatorname {Q}(\ell )$. If o does not intersect v=v _αα′ then o is included in the convex hull of α and α′ and we just ignore o: Σ(ℓ′)=Σ(ℓ), $\operatorname {Q}(\ell')=\operatorname {Q}(\ell )$ and $\operatorname {v}_{*}(\ell')= \operatorname {v}_{*}(\ell )$. Otherwise we insert o into $\operatorname {Q}$, and update Σ: we split Σ at v, and we regard the two resulting parts as stacks of arcs whose respective heads are the arcs contributed by α and α′. Then we pop from the left-hand stack until an arc β, say supported by body o′, is met such that o′ is the central body or v=v _o,o′ reaches β. Similarly we pop from the right-hand stack until an arc β′, say supported by body o″, is met such that v″=v _o″o reaches β′. Then, we shorten β and β′: the source of β and the sink of β′ are replaced with v _oo′ and v _o″o , respectively. Then, to build Σ(ℓ′), we concatenate what is left of the two stacks, with the arc, say δ, of ∂o with source v _o″o and sink v _oo′ in between. When an arc that follows the arc a(ℓ) that $\operatorname {v}_{*}(\ell)$ reaches (included) in Σ(ℓ) is popped, its supporting body is removed from $\operatorname {Q}$. If r(ℓ) is removed from $\operatorname {Q}$, and the body supporting the predecessor of δ along Σ(ℓ′) intersects ℓ′ at the right of o, we insert it into $\operatorname {Q}$, so that it becomes r(ℓ′) instead of o. If r(ℓ) is removed from $\operatorname {Q}$, and the body supporting the predecessor of δ along Σ(ℓ′) does not intersect ℓ′ at the right of o, o becomes r(ℓ′). Assume now that o is to the right of r. We discard o when o is included in the current convex hull, that is, if o is included in the convex hull of r,r _∗ and r ^∗. Otherwise, we proceed as in the previous case, except that we split Σ(ℓ) through the arc a that $\operatorname {v}_{*}(\ell)$ reaches instead of bitangent v _α′α (that is, there is one copy of a at the head of both stacks), and a body is removed from $\operatorname {Q}$ only if an arc it supports is popped from the left-hand stack. The body μ supporting the predecessor of δ along Σ(ℓ′) is inserted into $\operatorname {Q}$ if a(ℓ) has been popped from the right-hand stack and μ intersects ℓ′ at the right of o. Finally concerning the leave events only leave events for r need to be processed. The processing of those events simply consists of removing r from $\operatorname {Q}$.

Finally we mention that if, instead of working in a 4-sheeted covering, we work in a 3-sheeted covering, and lift the bodies accordingly, then the convex hull of the lifts still contains the convex hull of the bodies as a factor but our criterion to locate efficiently this factor breaks down; see Fig. 28 for an illustration.

Fig. 28

Three sheets are not enough

3.2 Cross-Section Algorithm

As said in the introduction our cross-section algorithm is a sweep of the convex hull of the bodies by a half-line whose supporting line is a left tangent at the origin of the half-line to a distinguished boundary body. The sweep starts at a distinguished boundary bitangent line segment leaving the distinguished boundary body (there might be several), and during the sweep we construct the cross-section of the visibility complex of the family of bodies with constraints assigned to the distinguished boundary bitangent line segment. The construction of the cross-section boils down to maintaining during the sweep the ordered sequence of forward and backward views² of the lines of free space supported by the sweeping half-line, that is, whose second coordinate is the sweeping half-line. However, it is asking to much of our chirotope because a view might start or (not exclusive) end at the endpoint of a constraint, and we have already observed that the relative positions of the endpoints of the constraints with respect to the bitangents are not completely determined by the chirotope of the convex bodies. To overcome this difficulty we are going to embed the views into larger boundary curves—called paths in the sequel—that start and end only at the touching points of the sweep half-lines with the convex bodies, and not at the endpoints of the constraints. So we reduce the problem of computing the cross-section to the problem of maintaining during the sweep the ordered sequence of paths pierced by the sweeping half-line—each path being represented by a subpath of constant complexity, called its window, because contrary to the sum of the complexities of the views the sum of the complexities of the paths is not necessarily linear. We let the (standard) details of the maintenance of the pierced paths by the sweep half-line to the reader and we concentrate on the definition of the paths and on the definition of their associated windows.

Assume without loss of generality that o ₀ is a boundary body and that the sweep is done around o ₀. Let G be the geometric graph union of the boundaries of the convex bodies o _i (except o ₀) and the constraints τ _i (we delete from the set of constraints the constraints incident to the body o ₀). Let m _i and M _i be the touching points with the body o _i of the left–left and left–right bitangents joining o ₀ to o _i ; similarly let a _i and A _i be the touching points with the constraint τ _i of the left–left and left–right bitangents joining o ₀ to τ _i . The points m _i and M _i split the boundary of o _i into two arcs g _i and d _i where by convention d _i joins m _i to M _i when walking counterclockwise around the boundary of o _i . The arcs g _i and d _i are oriented from m _i to M _i , and the constraint τ _i is oriented from a _i to A _i . This turns the graph G into a directed acyclic graph that is monotone with respect to sweeping half-line coordinate. We construct a new geometric graph G′ in two steps: for every body o _i we firstly add to G the chords of o _i joining (1) m _i to M _i , (2) m _i to every a _j ∈∂o _i , and (3) every A _j ∈∂o _i to the first a _k ∈∂o _i that follows, if any; A _j to M _i otherwise—and secondly we delete the body boundary edges of G. (See Fig. 29 for an illustration.) The unique maximal monotone path in G′ whose first constraint atom is τ _j is denoted p(τ _j ); similarly the path reduced to the chord joining m _i to M _i is denoted p(o _i ). The set of paths p(τ _j ) and p(o _i ) is denoted $\mathcal {P}$.

Fig. 29

Construction of the geometric graph G′

We now introduce the window of a path assigned to a sweeping half-line. Let p be a path of $\mathcal {P}$ and let ℓ be a sweeping half-line piercing the path p, let o′ be the first body pierced by ℓ among the bodies—contributing for a chord to the path p—lying at the right of the path p and let c′ be a chord of the path p supported by o′; similarly let o″ be the last body pierced by ℓ among the bodies lying at the left of the path p and let c″ be a chord of the path p supported by o″. We define a set of at most six chords $\epsilon_{j},\epsilon'_{j}$, j=1,2,3, as follows: (1) ϵ ₁ is the highest chord of the path p supported by a body below ℓ, ϵ ₂ is the highest chord of the path p below c′ supported by a body pierced by ℓ and following (strictly) o′, and ϵ ₃ is the highest chord below c″ supported by a body pierced by ℓ and preceding o″; and similarly (2) $\epsilon'_{1}$ is the smallest chord of the path p supported by a body above ℓ, $\epsilon'_{2}$ is the lowest chord above c′ supported by a body pierced by ℓ and following (strictly) o′, and $\epsilon'_{3}$ is the lowest chord of the path p above c″ supported by a body pierced by ℓ and preceding o″. The window of the path p at ℓ is denoted f(p,ℓ) and is defined as the subpath of p defined as the intersection of the paths p, p ₊(ϵ _j ) and $p_{-}(\epsilon'_{j})$, j=1,2,3, where for any chord c of the path p, the subpath p ₊(c) is the suffix subpath of p starting at the constraint following c and similarly the subpath p ₋(c) is the prefix subpath of p ending at the constraint preceding c. A simple case analysis leads to the following theorem.

Theorem 3.1

Let p be a path of $\mathcal {P}$ pierced by the sweeping half-line ℓ. Then the subpath f(p,ℓ) of p is well-defined, contains at most two chords, and is pierced by the half-line ℓ.

It remains to recall the definition of the views and to embed the views into the paths. Let S be the surface obtained by cutting the free part of the convex hull of the bodies along the constraints—note that S is not necessarily connected. The cusp points of ∂S (one cusp point $\hat{x}$ per endpoint x of constraint) and the extreme points m _i ,M _i of the bodies induce a natural decomposition of ∂S into monotone convex paths v _i , called the views. There are two views per vertex a _i —a view B(a _i ) whose first atom is the constraint leaving $\hat{a}_{i}$ and a view A(a _i ) whose first atom is an arc leaving $\hat {a}_{i}$—and also two views per vertex m _i —a view F(m _i ) whose first atom is a subarc of g _i leaving m _i and a view B(m _i ) whose first atom is an subarc of d _i leaving m _i , see Fig. 30 for an illustration. Let τ _i be a constraint leaving the convex body o _j . The view B(a _i ) is assigned to the path p(τ _i ) and the view A(a _i ) is assigned to the path $p(\tau'_{i})$ where $\tau'_{i}$ is the constraint leaving o _i that follows τ _i , if any; to the path p(o _j ) otherwise. The forward view F(m _i ) is assigned to the path p(τ _j ) where τ _j is the first constraint leaving g _i if any; to the path p(o _i ) otherwise. Similarly the view B(m _i ) is assigned to the path p(τ _j ) where τ _j is the first constraint leaving d _i if any; to the path p(o _i ) otherwise. Note that exactly two views are therefore assigned to a path.

Fig. 30

The views

3.3 Greedy Pseudotriangulation Algorithm

The input of the greedy pseudotriangulation algorithm is a cross-section Γ(J) of the visibility complex of the set of convex bodies ${\mathcal{D}}$ and the restriction of the sink bitangent line segment operator to the subset of 2-cells of that cross-section whose sink bitangent line segments are boundary bitangent line segments.

We denote by ≪ the partial order on $\mathcal {F}= \mathcal {F}(J)$ defined by σ≪σ′ if there is an edge-path in Γ(J) with source σ and sink σ′ (recall that the cross-section is acyclic). Let now < be a partial order on $\mathcal {F}$ compatible with ≪ on the sets $\mathcal {F}_{\{1,2\}3}$ and $\mathcal {F}_{12}$, compatible with the dual order ≪_∗ on the sets $\mathcal {F}_{3\{1,2\}}$ and $\mathcal {F}_{21}$, and such that

$$ \mathcal {F}_{33}<{ \mathcal {F}_{3\{1,2\}}\cup \mathcal {F}_{\{1,2\}3}} < { \mathcal {F}_{22}} < { \mathcal {F}_{12}\cup \mathcal {F}_{21}} < { \mathcal {F}_{11}}. $$

(11)

Our algorithm maintains the directed graph Γ(J), the restriction $\operatorname {sink}_{\mathcal {J}}$ of the $\operatorname {sink}$ operator to $\mathcal {J}$ and the restrictions to $B(\mathcal {J})= B_{\operatorname {forw}}(\mathcal {J}) \cup B_{\operatorname {back}}(\mathcal {J})$ of the operators $p_{\operatorname {forw}}$ and $p_{\operatorname {back}}$ when $\mathcal {J}$ describes a maximal chain of down-sets in the interval $[\emptyset,\mathcal {F}]$ (here $B_{\operatorname {forw}}(\sigma)$ and $B_{\operatorname {back}}(\sigma)$ are the orbits of the sink bitangent line segment of σ under $p_{\operatorname {forw}}$ and $p_{\operatorname {back}}$, respectively).

Let $\mathcal {J}$ be a down-set of $(\mathcal {F},<)$. Let σ be a minimal element of $\mathcal {F}\setminus \mathcal {J}$ whose sink bitangent line segment t is not a boundary bitangent line segment. We explain how to compute $B' = B(\mathcal {J}\cup\{\sigma\})$ from $B =B(\mathcal {J})$. Thanks to the conjugation relations $\mathcal {F}_{ij} \circ \iota = \iota \circ \mathcal {F}_{ji}$ it is sufficient to examine the cases $\sigma\in \mathcal {F}_{ij}$ with i≤j. Assume first that $\sigma\notin \mathcal {F}_{13}$. In that case one can easily check that B′=B∪{t} and that linked representations of and are computable in constant time (cf. Theorem 2.17 and Theorem 2.18). So it remains to explain how to compute t efficiently. We postpone this point to the next paragraph. Assume now that $\sigma\in \mathcal {F}_{13}$. In that case B∪{t} might be a proper subset of B′; so our goal is now not only to compute t but also its orbit under $p_{\operatorname {back}}$ (its orbit under $p_{\operatorname {forw}}$ reduces to t since t is right–right of left–right). We proceed as follows. Let σ ₁,σ ₂,…,σ _k+1 with k≥1 be the sequence of 2-cells defined by σ ₁=σ, $\sigma_{i+1}= \operatorname {dl}_{J}(\sigma_{i})$, $\sigma_{2},\ldots, \sigma_{k} \in \mathcal {F}_{12}$, and $\sigma_{k+1} \in \mathcal {F}_{\{2,3\}2}$, or $= \hat {0}$. Assume to fix the ideas that $\sigma_{k+1} \in \mathcal {F}_{22}$, that its forward view is a body, and that the backward view of the σ _i is a body (the other cases can be treated similarly). In that case $\operatorname {dl}_{J}(\sigma_{k+1}) \in \mathcal {F}_{\{1,2,3\}3}$ belongs to $\mathcal {J}$, the bitangent line segments of the sequence $\operatorname {H}^{+}_{\operatorname {rc}}(\sigma_{k+1};J)$ are bitangent line segments of B, and a linked representation of is computable in constant time. Assume for a moment that the 2-cells $\operatorname {ur}_{J}(\sigma_{i})$ (2≤i≤k+1) are in $\mathcal {F}_{33}$. In that case the , i=2,3,…,k+1, are computable in constant time. Therefore one can compute successively the sinks of the σ _i as the bitangent line segments joining the to the for i=k+1,k,…,2,1. Now we drop the assumption that the σ _i are elements of $\mathcal {F}_{33}$. Let s _i be the terminal segment of a line $t_{i} \in \operatorname {top}_{J}(\sigma_{i})$, let $s'_{i}$ be the right lift of s _i in the visibility complex of $\lambda_{s_{2}} \circ\cdots\circ \lambda_{s_{k+1}}({\mathcal{D}})$, and let $\widehat{J}$ be the antichain $\lambda_{s_{2}} \circ\cdots\circ\lambda_{s_{k+1}}(J)$. Let $\widehat{\sigma}_{i} = \operatorname {drf}(s'_{i})$ (i=2,3,…,k+1) and let $\widehat{\sigma}_{1} = \operatorname {ulf}(s'_{2})$. Using similar arguments to the ones given in the proof of Theorem 2.14 one can prove that the orbit of the sink bitangent line segment of σ ₁ under $p_{\operatorname {back}}$ coincides with the orbit of the sink bitangent line segment of $\widehat{\sigma }_{1}$ under $p_{\operatorname {back}}$; furthermore $\operatorname {ur}_{\widehat{J}}(\widehat{\sigma}_{i}) \in \mathcal {F}_{33}(\widehat{J})$, 2≤i≤k. Therefore one can proceed exactly as in the case $\operatorname {ur}_{J}(\sigma_{i}) \in \mathcal {F}_{33}$ but with the $\widehat{\sigma}_{i}$. The cost of this computation is a big-O of k plus the size of the prefix part of $\operatorname {H}^{+}_{\operatorname {rc}}(\operatorname {dl}_{J}(\sigma_{k+1});J)$ involved in the computation, which sum up to a O(n) when σ ranges over $\mathcal {F}_{13}$.

It remains to explain how to compute the bitangent that leaves and enters in O(1) amortized time. We will charge the cost on the bitangent line segments of the greedy pseudotriangulation $\operatorname {G}(J)$ associated with the cross-section. Recall (cf. [36]) that a bitangent $u\in \operatorname {G}(J)$ is said to be right-minimal if u is the ≺-minimal element of the set of bitangent line segments that appear in the boundary of the pseudotriangle of $\operatorname {G}(J)$ lying locally to the right of u; in that case this pseudotriangle is independent of J and is denoted $\operatorname {R}(u)$. Similarly a bitangent $u\in \operatorname {G}(J)$ is said to be left-minimal if u is the ≺-minimal element of the set of bitangent line segments that appear in the boundary of the pseudotriangle of $\operatorname {G}(J)$ lying locally to the left of u; in that case this pseudotriangle is independent of J and is denoted $\operatorname {L}(u)$. Clearly the sum of the complexities of the $\operatorname {R}(u)$ and $\operatorname {L}(u)$ for u right or left-minimal in $\operatorname {G}(J)$ is linear in the size of $\operatorname {G}(J)$, that is, a O(n). Let e ₁ e ₂…e _k and $e'_{1}e'_{2}\ldots e'_{k'}$ (k,k′≥1) be the sequences of (oriented) arcs of the chains and , and let e _m and $e'_{m'}$ be the arcs that t enters and leaves. The source and the sink of e _i are denoted v _i and v _i+1. Note that for i=2,3,…,k the bitangent v _i is an atom of the chain . For i=2,…,k, let T _i be one of the two pseudotriangles of size two adjacent to along the bitangent v _i and let u _i be the bitangent joining T _i to ; it is convenient to denote by u ₁ the source of μ(σ). Clearly u _i enters —which has constant complexity³—and u _i is computable in constant time. The bitangent line segments u _i decompose the pseudopolygon —which reduces to in case k=1—into k pseudotriangles R ₁,…,R _k where R _i lies locally to the left of the bitangent u _i (1≤i≤k). Note that the number of bitangent line segments lying in the boundary of R _i is a O(1) (except for R ₁ in the case $\sigma\in \mathcal {F}_{11}$). We define inductively the sequences $R^{*}_{i}, u^{*}_{i}$ (i=1,…,k ^∗) as follows:

• (1) and we define $u_{1}^{*}$ as the bitangent joining $R^{*}_{1}$ to R ₁,

• (2) if $u_{i}^{*}$ enters the arc e _i or the arc e _k then k ^∗=i and we are done; otherwise we define $R^{*}_{i+1}$ to be the right pseudotriangle of $u^{*}_{i}$ in the pseudoquadrangle $R^{*}_{i} \cup R_{i}$ and we define $u_{i+1}^{*}$ to be the bitangent joining $R^{*}_{i+1}$ to R _i+1.

Clearly the sequences $R^{*}_{i}, u_{i}^{*}$ are well-defined; $R^{*}_{i}$ and R _i are adjacent along the bitangent u _i ; t is the last term of the sequence of $u^{*}_{i}$ (that is, $t= u^{*}_{k^{*}}$); $u_{i}^{*}$ leaves one of the arcs, say $e'_{m^{*}_{i}}$, of the sequence $e'_{1} \ldots e'_{k'}$; $m^{*}_{1} \geq m^{*}_{2} \geq\cdots\geq m'$. Consequently t is computable in time $O(m+m_{1}^{*})$. Let now t′ be the sink of $\operatorname {top}(\sigma)$. A simple case analysis shows that either t=t′, m=1 and $m'=m_{1}^{*}$; or t≠t′, m≥2, t′ is a bitangent of , t′ is left- or right-minimal in $\operatorname {G}(J)$ depending on whether lies locally on the left or on the right side of t′, and m and $m^{*}_{1}-m'$ are bounded by the size of $\operatorname {L}(t')$ or $\operatorname {R}(t')$ depending on whether lies locally on the left or on the right side of t′. Its follows that $\sum_{\sigma\in \mathcal {F}^{\circ }(J)} \{m(\sigma) + m_{1}^{*}(\sigma)\} = O(n)$. This prove that t is computable in constant amortized time.

4 Conclusion and Open Problems

We have presented an efficient algorithm to compute a pseudotriangulation of a planar (well-constrained) finite family of pairwise disjoint convex bodies with constraints presented by its chirotope. Its running time is a O(nlogn) where n is the number of convex bodies of the family. We expect to prove its practical efficiency in a forthcoming implementation. The design of our pseudotriangulation algorithm relies on an extension of the theory of pseudotriangulations and visibility complexes to the setting of branched coverings of topological planes. We conclude by a sequence of open problems raised by this work. Can we extend our pseudotriangulation algorithm to not necessarily well-constrained family of convex bodies keeping the same time bound on its running time? Can we sweep efficiently the dual arrangement of a finite planar family of convex bodies presented by its chirotope using only linear space? According to the main result of the paper this problem boils down in O(nlogn) time to sweeping the arrangement of the dual pseudolines of the pseudotriangles of a pseudotriangulation of the family of convex bodies; this arrangement is an arrangement of pseudolines with contact points to which it is tempting to apply the topological sweep method of Edelsbrunner and Guibas [13]; however, the fact that the chirotope of the pseudolines is not computable in constant time (since the pseudolines do not have constant complexities) prevents a naive application of the topological sweep method. Can we enumerate the pseudotriangulations of a planar family of convex bodies presented by its chirotope in sublinear time per pseudotriangulation using only linear space? Does the complex of pseudotriangulations of a planar family of pairwise disjoint convex bodies is a (shellable) sphere? a matroid polytope? a polytope? It is known to be a polytope for families of bodies lying in the classical real affine plane [40]. Finally we observe that these questions can be asked not only for families of convex bodies of topological planes but also for families of convex bodies of branched coverings of topological planes.

Appendices

Appendix A: Duality in Topological Planes

1.1 A.1 Topological Planes

A topological plane on ℝ² is a surface homeomorphic to ℝ² endowed with a topological point-line incidence geometry whose line space is a subspace of the space of pseudolines of the surface satisfying the so-called linear space axiom: any two distinct points p and q are contained in exactly one line p∨q, their joining line. It is known that the line space of topological plane is a open crosscap, that is, a surface homeomorphic to $\mathbb{RP}^{2}$ with one point deleted, as illustrated in the right circular diagram of Fig. 31 where the antipodal boundary points are identified and where the marked point (∞) plays the role of the deleted point. A topological plane is called affine if for every point-line pair (p,l) there exists a unique line k through the point p that coincides with the line l or has no point in common with it; the line k is called the parallel to l through p. Classical examples of topological planes are

• (1) the real affine plane or classical topological plane defined as the affine topological plane whose set of points is ℝ² and whose set of lines is the set of curves with equations y=ax+b, a,b∈ℝ, and x=c, c∈ℝ; the real affine plane is the default plane in the field of discrete and computational geometry;

• (2) the Moulton planes obtained by starting from the real affine plane and replacing the lines of the real affine plane with negative slope by the kinked lines {(x,y)∣y=ax+b,x≥0}∪{(x,y)∣y=akx+b,x≤0}, a∈ℝ⁻,b∈ℝ, where k>1 is a fixed parameter;

• (3) the Klein model of the real hyperbolic plane defined as the restriction of the real affine plane to the open unit disk; and

• (4) the so-called arc planes which include examples of topological planes with no embedding into any affine topological plane, e.g., start with the real affine plane and replace the lines with positive slope by the shifted arcs {(x,y)∈ℝ²∣y−n=e ^x−m}, m,n∈ℝ.

The projective completion of the real affine plane is the unique desarguesian projective topological plane on $\mathbb{RP}^{2}$, a characterization due to Hilbert, 1899. The Moulton planes are examples of non-desarguesian affine topological planes. We refer to [9, 17, 38, 41] for a more detailed background material on topological planes, and for the precise meaning of the terms used above (topological projective planes, projective completion, desarguesian, etc.) but not defined explicitly.

Fig. 31

A topological plane

1.2 A.2 Duality

We work in an oriented topological plane on ℝ². The term duality refers to the map that assigns to a point of the plane the pencil of lines through that point, embedded in the line space of the plane, and more generally to the map that assigns to a convex body of the plane its set of tangent lines. The basic properties of the duality map for points relevant to our purpose are the following:

• (1) the dual of a point is a pseudoline, that is, a simple closed curve homotopic to a, hence any, generator of the fundamental group of the line space or, equivalently, a non-separating simple closed curve;

• (2) the dual family of a family of points is an arrangement of pseudolines, that is, a finite family of pseudolines living in the same open crosscap with the property that any two cross in exactly one point;

• (3) the isomorphism class of the dual family of a family of points depends only on the chirotope of the family of points and vice versa; and

• (4) any arrangement of pseudolines is isomorphic to the dual family of a planar family of points.

Figure 32 shows the dual arrangements of the five families of three points realizing the five possible chirotopes on a given indexing set of size three depicted in Fig. 1. In this figure the line space is represented by a circular diagram with antipodal boundary points identified, one marked point (∞) in the role of the deleted point, and one arrow on the boundary of the circular diagram to indicate which of the two generators of the fundamental group of the line space is the one that fits via duality the orientation of the topological plane. According to the third basic property of the duality map of points mentioned above the chirotope of a planar family of points can be coded by the isomorphism classes of the subarrangements of size three of its dual arrangement. In general the isomorphism class of an arrangement of pseudolines γ ₁,γ ₂,…,γ _n can be coded by the poset of its cells ordered by inclusion or, equivalently, by its side cycles: C ₁,C ₂,…,C _n where C _i is the circular sequence of signed indices of the pseudolines crossed by the side wheel of a sidecar rolling on γ _i , according to its orientation, with the convention that an index is signed positively or negatively depending on whether the crossed pseudoline is (locally) directed towards or away γ _i . For example the side cycles of the arrangements of Fig. 32 labeled A and B are

$$\begin{array}{l@{\quad}l} 1{:} & 23\overline {2}\overline {3}\\ 2{:} & 31\overline {3}\overline {1}\\ 3{:} & 12\overline {1}\overline {2}\end{array} \quad\text{and} \quad \begin{array}{l@{\quad}l} 1{:} & \overline {3}3\overline {2}2\\ 2{:} & 13\overline {3}\overline {1}\\ 3{:} & \overline {1}12\overline {2}, \end{array} $$

respectively, and those of A′,B′ and B″ are obtained from those of A and B by suitable permutations of the indices.

Fig. 32

The dual arrangements of the five families of three points realizing the five possible chirotopes on a given indexing set of size three depicted in Fig. 1

In the companion paper [19, 20] we show that the above properties of the duality map for points extend to the duality map for convex bodies in the following terms:

• (1) the dual of a convex body is a double pseudoline, that is, a simple closed curve homotopic to the double of a, hence any, generator of the fundamental group of the line space;

• (2) the dual family of a family of pairwise disjoint convex bodies is an arrangement of double pseudolines, that is, a finite family of double pseudolines living in the same open crosscap, with the property that any two meet exactly four times, meet transversely exactly four times, and induce a cell structure on the one-point compactification of the crosscap;

• (3) the isomorphism class of the dual family of a family of pairwise disjoint convex bodies depends only on the chirotope of the family of bodies and vice versa; and

• (4) any arrangement of double pseudolines is isomorphic to the dual family of a planar family of pairwise disjoint convex bodies.

For example the arrangement of three double pseudolines depicted in the right diagram of Fig. 33 is a representative of the isomorphism class of the dual arrangement of the family of three convex bodies depicted in the left diagram of Fig. 33 (the two black vertices are the two tritangents of the family). As for arrangements of pseudolines an arrangement of double pseudolines can be coded by the poset of its cells ordered by inclusion or by its side cycles which are defined similarly, except that there are now two side cycles per index since a double pseudoline has, contrary to a pseudoline, two sides: a crosscap side and a disk side; thus the side cycle of crosscap type of the arrangement of Fig. 33 is

$$\begin{array}{l@{\quad}l} 1{:} & \overline {2}\overline {3}\overline {3}\overline {2}2332\\ 2{:} & \overline {3}1\overline {3}1\overline {1}3\overline {1}3\\ 3{:} & 2112\overline {2}\overline {1}\overline {1}\overline {2}\end{array} $$

and the one of disk type is

$$\begin{array}{l@{\quad}l} 1{:} & 2323\overline {3}\overline {2}\overline {3}\overline {2}\\ 2{:} & 33\overline {1}\overline {1}11\overline {3}\overline {3}\\ 3{:} & \overline {1}\overline {2}\overline {1}\overline {2}2121. \end{array} $$

Observe that for a simple arrangement the side cycle of disk type and the side cycle of crosscap type are the negatives of each other.

Fig. 33

A family of three pairwise disjoint convex bodies and its dual arrangement

Figure 34 depicts representatives of the 22 isomorphism classes of non indexed simple arrangements of three double pseudolines: Each diagram is labeled at its left bottom corner with a symbol to name it (of type M _α where α is the 2-sequence of its numbers of 2-cells of size 2 and 3 possibly followed, in brackets, with the size of the unbounded 2-cell of the arrangement in the case where there are several arrangements with the same 2-sequence; M _α and $M_{\alpha}^{\star }$ are mirror images of one another) and is labeled at its right bottom corner with the size of its automorphism group; thus the number (118) of simple chirotopes of families of three pairwise disjoint convex bodies on a given indexing set of size 3 can be computed as the sum

$$\sum_{k\geq1} \frac{3!}{k} g_k = \frac{6}{1} \times18 + \frac{6}{2} \times2 + \frac{6}{3} \times2 $$

where g _k is the number of arrangements of Fig. 34 with group of automorphisms of order k.

Fig. 34

Representatives of the 22 isomorphism classes of simple non indexed arrangements on three double pseudolines

Appendix B: Perturbation scheme

Our purpose of this section is to give a detailed proof of the following (intuitively clear) theorem.

Theorem B.1

Let χ be a non-simple chirotope of planar families of pairwise disjoint convex bodies. Then there exists a simple chirotope χ ^∗, computable in constant time, such that χ and χ ^∗ have the same set of pseudotriangulations.

Our proof is based on (1) the one-to-one and onto correspondence, induced by the duality map, between the class of chirotopes of finite planar families of disjoint convex bodies and the class of chirotopes of arrangements of double pseudolines [19]; cf. Appendix A; (2) the dual characterization of the class of pseudotriangulations of a finite planar family of disjoint convex bodies of Pilaud and Pocchiola [32]; and on (3) the classical interpretation of simple pseudoline arrangements as non redundant primitive sorting networks [24, Sect. 5.3.4], [25, page 29], [11].

By a pseudotriangulation of a double pseudoline arrangement ∇ living in an open crosscap we mean a pseudoline arrangement with contact points $\mathcal{L}$, that is, a finite family of pseudolines that intersect pairwise in a finite number of points of which exactly one is a transversal intersection point, with the property that $\bigcup\mathcal{L}$ covers exactly the topological closure of ⋃∇ minus the first level of the arrangement ∇ with respect to its non-compact face. Figure 35 depicts a non-simple arrangement of three double pseudolines 1,2 and 3 and one of its pseudotriangulation a,b,c,d (red, blue, green and purple in pdf color): the vertices that support a contact point are marked with a disk (yellow in pdf color); the non-simple vertex supports only one contact point; this contact point is a contact point between the pseudolines b and c.

Fig. 35

A non-simple arrangement of three double pseudolines and one of its pseudotriangulations

Theorem B.2

(Pilaud and Pocchiola [32])

Let Δ be a finite planar family of pairwise disjoint convex bodies, let ∇ be its dual arrangement, and let Φ be the map that assigns to a pseudotriangulation of Δ the arrangement of the dual pseudolines of its pseudotriangles. Then Φ realizes a one-to-one and onto correspondence between the set of pseudotriangulations of Δ and the set of pseudotriangulations of ∇.

Proof

For completeness and clarity we repeat the proof of [32] (which considers only convex bodies in general position). That Φ is well-defined and one-to-one and that its range is included in the set of pseudotriangulations of ∇ was explicitly observed in [34]. To prove that the range of Φ is exactly the set of pseudotriangulations of ∇ we use a simple counting argument involving the tangency and winding numbers. Let Δ ₁,Δ ₂,…,Δ _n be the convex bodies of Δ and let $\mathcal {T}_{1},\mathcal {T}_{2},\ldots,\mathcal {T}_{2n-2}$ be the envelopes of the pseudolines of a pseudotriangulation of ∇. Our goal is to prove that the $\mathcal {T}_{i}$ are the boundaries of the pseudotriangles of a pseudotriangulation of Δ. This boils down to proving that for any point x avoiding the boundaries of the Δ _i and $\mathcal {T}_{i}$

$$ \sum_{i=1}^{2n-2} w(x, \mathcal {T}_i) = \begin{cases} 1 & \text{if $x \in\varDelta_{0}\setminus\bigcup_{i=1}^{n} \varDelta_{i}$}, \\ 0 & \text{otherwise} \end{cases} $$

(12)

where $w(x, \mathcal {T}_{i})$ is the winding number of x with respect to $\mathcal {T}_{i}$ and where Δ ₀ is the convex hull of the Δ _i . Introduce in the picture the tangency number $t(x,\mathcal {T}_{i})$ of a point x with respect to $\mathcal {T}_{i}$ as the number of tangents to $\mathcal {T}_{i}$ through x or, to put it differently, as the number of intersection points between the dual pseudolines of x and $\mathcal {T}_{i}$. Similarly introduce in the picture the tangency number t(x,Δ _i ) of x with respect to Δ _i . The reader will easily check that

$$ \sum_{i =1}^n t(x, \varDelta_i) = t(x,\varDelta_0) + \sum _{i = 1}^{2n-2} t(x,\mathcal {T}_i); $$

(13)

that t(x,Δ _i )=0 or 2 depending on whether x belongs to the interior or to the exterior of Δ _i ; and finally that $t(x,\mathcal {T}_{i}) = 1+ 2 w(x,\mathcal {T}_{i})$. Equation (12) follows easily. □

Proof of Theorem B.1

Let Γ be a realization of χ as a double pseudoline arrangement. We define χ ^∗ as the chirotope of an arrangement of double pseudolines Γ ^∗ obtained Γ by a sequence of mutations. Let v be a non-simple vertex of Γ with degree 2k, k≥3. In the vicinity of v the arrangement Γ is isomorphic to a pencil of pseudolines ℓ ₁,ℓ ₂,…,ℓ _k of the unit disk as indicated in the left diagram of Fig. 36 where each pseudoline is oriented from left to right and where each pseudoline (except ℓ ₁ and ℓ _k for which the information is not relevant) bears a distinguished side—indicated by a rectangle in the figure—which corresponds to the Möbius side of the corresponding double pseudoline. We perturb the pencil ℓ _i in the vicinity of its vertex into the unique cyclic arrangement $\ell'_{i}$ with the property that the pseudoline $\ell'_{i}$ contributes to the upper or lower envelope of the arrangement depending on whether its Möbius side contains the south or north pole of the unit disk, as illustrated in the right diagram of Fig. 36. Carrying back this perturbation on Γ we get an arrangement Γ′ whose number of non-simple vertices is one less than the number of non-simple vertices of Γ. This perturbation is clearly compatible with the isomorphism relation and stable under taking subarrangement, that is, for any J⊂I the restriction to J of the arrangement Γ′ is isomorphic to the perturbed version of the restriction of Γ to J: more formally (Γ′) _J =(Γ _J )′. In particular the chirotope of the perturbation of Γ is the perturbation of the chirotope of Γ; this proves that χ′ is computable in constant time. Repeating this perturbation at each non-simple vertex of the arrangement Γ we get a simple arrangement Γ ^∗ whose chirotope χ ^∗ is computable in constant time. It remains to show that χ and χ′ (hence χ ^∗) have the same set of pseudotriangulations. Let $\mathcal{L}$ be a pseudotriangulation of Γ. We construct a pseudotriangulation $\mathcal{L}'$ of Γ′ which coincides with $\mathcal{L}$ except in the vicinity of v. Let σ be the permutation of {1,2,…,k} that maps the index i on the index j defined by the condition that the pseudoline of $\mathcal{L}$ (or the first level of Γ) entering v along ℓ _i leaves v along ℓ _j . Now we interpret the arrangement of lines $\ell'_{i}$ as a primitive sorting network to carry the keys σ(i) from the left endpoints of the ℓ _i to the right endpoints of the ℓ _σ(i) [25, page29]; this yields to a touching or crossing status to each vertex of the arrangement $\ell'_{i}$ depending on whether the corresponding comparator is feeded with entries in sorted order or not and, therefore, to a pseudotriangulation $\mathcal{L}'$ of Γ′ which coincides with $\mathcal{L}$ except in the vicinity of v. For example if, in the example of Fig. 36, we take

then we sort (in decreasing order) the array [4,1,2,3,6,5,7] with the sorting network

corresponding to the arrangement $\ell'_{i}$. The sequence of comparisons and arrays obtained during the sorting process is then

(the comparators feeded with a pair of indices in sorted order are drawn dashed) which yields to a touching status for the vertices v ₁₂,v ₂₃,v ₃₄ and v ₅₆ of the arrangement $\ell'_{i}$ and to a crossing status for the other vertices, as indicated in Fig. 37 where the touching vertices are marked with a little (yellow in pdf color) disk. It remains to show that if $\mathcal{L}''$ is a pseudotriangulation of Γ′ which coincides with $\mathcal{L}$ except in the vicinity of v, then $\mathcal{L}'=\mathcal{L}''$. Let Δ′ be a realization of Γ′ as a planar family of convex bodies and let $\varDelta'_{i}$ be the convex body corresponding to the double pseudoline supported by $\ell'_{i}$. By construction the bitangent line segment b _ij supported by the line v _ij intersection of the curves $\ell'_{i}$ and $\ell'_{j}$, i<j, is free with respect to the $\varDelta'_{i}$ if and only if j=i+1 and the b _ii+1 are pairwise interior noncrossing. This prove that $\mathcal{L}'=\mathcal{L}''$ since the complex of pseudotriangulations is strongly flag connected.

Fig. 36

The perturbation scheme

Fig. 37

 

 □

Appendix C: Computing the Visibility Graph of a Set of Line Segments

In this section we show how visibility graphs of finite planar families of pairwise interior disjoint line segments (the so-called “polygons with holes” in the computational geometry literature [4, 15, 28, 29, 31]) fit into the theory of visibility complexes of families of pairwise disjoint convex bodies with constraints. To this end we embed the class of chirotopes of families of points into the class of chirotopes of families of convex bodies as follows. Define a thin chirotope as a chirotope of a family of convex bodies with the property that its restrictions to subfamilies of convex bodies pierced by a line are chirotopes of pencils of convex bodies (that is, families of disks with same radius and aligned centers of the classical topological plane), and let ζ be the map that assigns to a thin chirotope the conjunction of its left–left and right–right components—we call this way the maps that assign to a triple of indices the subvectors of its associated position vector whose entries are those defined with respect to the left–left and right–right bitangents, respectively. It is a simple exercise to check that the map ζ realizes a constant time computable one-to-one and onto correspondence between the class of thin chirotopes and the class of chirotopes of families of points. Furthermore for any thin chirotope, say realized by the family of convex bodies O={o _i }, the four-to-one map η that assigns to a bitangent line segment joining the bodies o _i to o _j the line segment joining the points ζ(o _i ) to ζ(o _j ) has an efficiently computable section ξ mapping a line segment on an interior bitangent line segment such that the visibility graph of the family of points ζ(O) with respect to a family of constraints K is the image under η of the visibility graph of the family of convex bodies O with respect to the family of constraints ξ(K). To see this we introduce a permutation q=q ₁ q ₂…q _n of the p _i with the property that there exists a line through q _i that separates the convex hull of the q _j , 1≤j≤i, from the convex hull of the q _j′, i<j′≤n—such a permutation is computable in O(nlogn) time as we shall see in the next section—and we define ξ as the map that assigns to the line segment joining ζ(o _i ) to ζ(o _j ) the bitangent line segment joining o _i to o _j whose oriented version with respect to the permutation q is right–left. The reader will easily check that the section ξ thus defined satisfies the property mentioned above. See Fig. 38 for an illustration. Therefore we get the following theorem.

Fig. 38

This figure suggests how visibility graphs of finite planar families of interior disjoint line segments fit into the theory of visibility complexes of well-constrained families of convex bodies

Theorem C.3

The visibility graph of a planar family of n pairwise interior disjoint line segments presented by the chirotope of the endpoints of the line segments is computable in $O(\mathit{size\ of\ the\ visibility\ graph + n \log n})$ time and linear working space.

We should mention that this mechanism of interpretation of visibility graphs of families of line segments by visibility complexes of families of convex bodies with constraints (that is, the embedding ζ, the map η and one of its sections ξ) is implemented in the visibility complex package of the CGAL library [2] (see also [3, Remark 5]) and explicitly used to design an enumeration algorithm for pointed pseudotriangulations of families of points in general position [8].

Appendix D: Computing a Pseudotriangulation of a Set of Points

In this section we explain how to compute a pseudotriangulation of a planar family of points presented by its chirotope. Let p ₁,p ₂,…,p _n be a finite planar family of n points, let q=q ₁ q ₂…q _n be a permutation of the p _i such that for any index i there is line through q _i that separates the convex hull of the q _j , 1≤j≤i, from the convex hull of the q _j′, i<j′≤n, and let ϵ be an orientation of the underlying plane. Note that such a permutation is computable in O(nlogn) time: pick an extreme point in O(nlogn) time using your favorite convex hull algorithm and sort the remaining points angularly around it. The Graham scan applied to the sequence q boils down to computing explicitly the map u=u _q,ϵ :{q ₂,q ₃,…,q _n }→{q ₁,q ₂,…,q _n−1} defined inductively by the relations

$$ \begin{cases} u_{}^{}{(q_2)} = q_1; & \\ u_{}^{}{(q_i)} = u_{}^{r_i}{(q_{i-1})} \end{cases} $$

(14)

where r _i is the first natural number r≥0 such that the triangle spanned by ordered triple of points $q_{i}, u_{}^{r}{(q_{i-1})}$, and $u_{}^{r+1}{(q_{i-1})}$ is counterclockwise or is not defined. For example the following table (where we write i for q _i )

i	2	3	4	5	6	7	8	9	10	11	12	13	14
r i	0	1	0	1	0	2	1	1	0	1	0	1	1
u(i)	1	1	3	3	5	3	3	3	9	9	11	11	11
s i	0	0	2	0	1	0	1	0	2	0	3	0	2
v(i)	1	2	1	4	4	6	6	8	6	10	4	12	4

depicts the map u and its relative v, obtained by reversing the orientation of the plane, associated with the family of 14 points p _i of the real affine plane with coordinates

and the permutation of the p _i obtained by sorting them according to the decreasing values of their vertical coordinates, as depicted at the left top corner of Fig. 39. From the map u _q,ϵ and its relatives u _q,−ϵ , u _−q,ϵ , u _−q,−ϵ , obtained by reversing the orientation of the plane or the permutation of the p _i or both, one can easily deduce, thanks to [36, Theorem 12, Claim 3], not only the convex hull of the p _i —under the form of the sequence $q_{n}, u_{}^{}{(q_{n})}, u_{}^{2}{(q_{n})}, \ldots, q_{1}$ and its relative obtained by reversing the orientation of the plane—but two pseudotriangulations (both pseudotriangulations are pointed in the case where the family of points is in general position). Indeed let $U_{q}^{\epsilon}$ be the set of line segments $q_{i}u_{}^{}{(q_{i})}$, 2≤i≤n, let v _i be the undirected version of the right–left bitangent line segment joining the convex hull of the q _j , i+1≤j≤n, to the convex hull of the q _j , 1≤j≤i and let $R_{q}^{\epsilon}$ be the set of v _i , 1≤i≤n−1. Then, as illustrated in Fig. 39,

• (1) $U_{q}^{\epsilon}$ is a spanning tree of the family of p _i and $U_{q}^{\pm\epsilon}$ is a pseudotriangulation of the family of p _i ; in the case where the points are in general position the tree $U_{q}^{\epsilon}$ is the primal version of the upper horizon tree of Edelsbrunner and Guibas [13];

  Fig. 39

  

  Computing a greedy pseudotriangulation of a set of points

• (2) $U_{\pm q}^{\epsilon}$ induces a decomposition of the convex hull of the family of p _i into pseudotriangles and pseudoquadrangles, and its completion by $R_{q}^{\epsilon}$ is a greedy pseudotriangulation of the family of p _i (this was first observed in [33]; see also [8, Lemma 11]).

It is also interesting to mention that if $T_{q}^{\epsilon}$ denotes the set of line segments $q_{i}u_{}^{r}{(q_{i-1})}$, 0≤r≤r _i ,2≤i≤n, then $T_{q}^{\pm\epsilon}$ is a triangulation of the convex hull of the family of p _i .