Intersections and circuits in sets of line segments

Abstract

Sets of straight line segments with special structures and properties appear in various applications of geometric modeling, such as scientific visualization, computer-aided design, and medical image processing. In this paper, we derive sharp upper and lower bounds on the number of intersection points and closed regions that can occur in sets of line segments with certain structure, in terms of the number of segments. In particular, we consider sets of segments whose underlying planar graphs are Halin graphs, cactus graphs, maximal planar graphs, and triangle-free planar graphs, as well as randomly produced segment sets.

1 Introduction

Sets of straight line segments with special structures and properties appear in various applications of geometric modeling, such as scientific visualization, computer-aided design, medical image processing, and geometric feature learning. In this paper, we derive sharp upper and lower bounds on the number of intersection points and closed regions that can occur in sets of line segments whose underlying planar graphs are Halin graphs, cactus graphs, maximal planar graphs, and triangle-free planar graphs. These bounds can be used to optimize the runtime of algorithms for combinatorial problems posed on such sets of segments.

Let M be a finite set of line segments of nonzero length drawn in the plane. Suppose there are no collinear segments that intersect (or treat such segments as a single segment). Let P(M) be the set of all intersection points of segments in M and J(M) be the set of endpoints of segments in M; note that $P(M) \cap J(M)$ may be non-empty. Let $G_M=(V(G_M),E(G_M))$ be the graph whose vertex set is $P(M)\cup J(M)$ and where vertices u and v are adjacent whenever there is a segment $s\in M$ that contains u and v, such that there is no $w \in (P(M)\cup J(M)) \cap s$ that is between u and v. Note that $G_M$ is a planar graph; unless otherwise stated, we will assume $G_M$ is endowed with the plane embedding specified by the drawing of M.

Let C(M) be the set of inclusion-minimal regions enclosed by closed simple polygonal curves in M; we will call the elements of C(M) circuits. By a circuit segment set of M we will mean the set of segments in M that contribute to a circuit of M by infinitely many points. There is a one-to-one correspondence between the circuits of M, the circuit segment sets of M, and the bounded faces of $G_M$. We will call a path-connected component of M trivial if it consists of a single segment, and nontrivial if it contains two or more segments. Given a segment $s\in M$, $M\backslash s$ denotes removing all non-intersection points of s from M (in other words, removing all points which are exclusively in s but keeping the points which also belong to other segments). Similarly, given a subset of segments $S=\{s_1,\ldots ,s_k\}\subset M$, $M\backslash S$ denotes $M\backslash s_1\backslash \ldots \backslash s_k$. We will also define $m(M)=|M|$, $p(M)=|P(M)|$, $j(M)=|J(M)|$, $c(M)=|C(M)|$, $n(M)=|V(G_M)|$, $e(M)=|E(G_M)|$, and $k_1(M)$ and $k_2(M)$ respectively as the number of trivial and nontrivial components of M. When there is no scope for confusion, dependence on M in all definitions will be omitted. The following are basic relations between the quantities defined above.

Observation 1

For any segment set M,

1.	$p\le {m\atopwithdelims ()2}$	Any pair of segments can intersect at most once.
2.	$c\le {m-1\atopwithdelims ()2}$	Each circuit has a leftmost intersection point.
3.	$e\ge m$	Each segment produces at least one edge.
4.	$n\le p+j$	Vertices of $G_M$ are intersection points or segment endpoints.
5.	$m\ge k_1+2k_2$	Trivial components have a single segment; nontrivial have at least two.
6.	$p\ge k_2$	Nontrivial components have at least one intersection point.

All bounds are sharp, i.e., there are classes of segment sets for which the bounds hold with equality.

Since every planar graph has an embedding where its edges are mapped to straight line segments (cf. Wagner 1936), for any planar graph G there exists a segment set M such that $G_M\simeq G$ (any edges incident to a degree 2 vertex v that are drawn as collinear segments in a straight-line embedding of G can be slightly shifted so that v becomes an intersection point). Thus, there is an equivalence between sets of line segments and planar graphs. Given a family ${\mathcal {F}}$ of planar graphs, we will refer to the family $\{M \text { is a set of segments}:G_M\in {\mathcal {F}}\}$ as segment-${\mathcal {F}}$. For instance, any set of segments with $c=0$ will be called a segment forest, and any set of segments that is path-connected and has $c=0$ will be called a segment tree. In general, graphs of the type $G_M$ (as defined earlier in this section) will be called segment graphs. For special classes of segment sets, the bounds from Observation 1 can be improved. The following are sharp bounds for some simple families of segment sets.

Observation 2

• 1. If M is a segment tree, $p\le m-1$ and $c=0$.

• 2. If M is a segment forest, then $p \le m-k_1-k_2$ and $c=0$.

• 3. If M is a segment unicyclic graph, then $p\le m$ and $c=1$.

Moreover, all bounds are sharp.

As an example of a nontrivial result of this kind, Poonen and Rubinstein (Poonen and Rubinstein 1998) computed p and c for sets of segments formed by the diagonals of regular polygons. A recent paper of Kumar (Kumar 2019) extends this investigation to sets of segments formed by the diagonals of convex polygons. A conference version of the present paper (Brimkov 2017) computed p and c for segment cactus graphs. See also (Dujmović et al. 2007; Durocher and Mondal 2018; Green and Tao 2013; Igamberdiev et al. 2015; Oliveros et al. 2020; Samee et al. 2008) for related questions on drawing planar graphs with few segments, and combinatorial properties of sets of lines and segments.

These kinds of bounds can be used to analyze the time and space complexity of algorithms for finding the intersections and bounded regions occurring in a set of segments in terms of m, p, and c; these are fundamental tasks in computational geometry and have been widely studied (cf. Balaban 1995; Bentley and Ottmann 1979; Chazelle 1983; Mairson and Stolfi 1988; Preparata and Shamos 2012; Tiernan 1970). For example, the algorithms of Bentley-Ottmann (Bentley and Ottmann 1979), Chazelle (Chazelle 1983), and Balaban (Balaban 1995), which compute all intersections in a given set of segments, have respective time complexities of $O((m+p) \log m)$, $O(p + \frac{m \log ^2 m}{\log \log m})$, and $O(p+m \log m)$, the last one being optimal for general segment sets. The worst case performance of these algorithms is achieved for sets of segments with $\Omega (m^2)$ intersections, and is respectively $\Omega (m^2 \log m)$ for Bentley-Ottmann’s algorithm, and $\Omega (m^2)$ for Chazelle’s and Balaban’s algorithms. However, as we show in the sequel, segment sets that feature a Halin or cactus structure have $p=O(m)$; thus, for these types of segment sets, Bentley-Ottmann’s and Balaban’s algorithms run in $O(m \log m)$ time and are superior to Chazelle’s algorithm, which runs in $O(\frac{m \log ^2 m}{\log \log m})$ time. As another example, Chen and Chan (Chen and Chan 2003) and Vahrenhold et al. (Bose et al. 2007; Vahrenhold 2007) presented in-place algorithms for finding all intersections in a set of segments (i.e., algorithms that use O(1) cells of memory in addition to the input array). The time complexity of these algorithms is $O((m +p) \log m)$ and $O(m \log ^2 m + p)$, respectively; for arbitrary segment sets, Vahrenhold’s algorithm is superior to Chen-Chan’s algorithm, as they respectively require $\Omega (m^2)$ and $\Omega (m^2 \log m)$ time in the worst case. However, for the aforementioned classes of segment sets, Chen-Chan’s algorithm runs in $O(m \log m)$ time and is superior to Vahrenhold’s algorithm which runs in $O(m \log ^2 m)$ time. The algorithms discussed above have various applications in imaging sciences and mathematical visualization, including for tasks like computer-aided geometric design, digital image restoration, image segmentation, and geographic information systems queries. Since these algorithms are sometimes applied to very large datasets, the complexity improvements that can be obtained from our bounds on p and c could lead to a notable reduction in runtime.

In some cases, there may be direct relations between p, c, and m. For example, in segment maximal outerplanar graphs¹, $p=c+2$; however, while maximal outerplanar graphs with n vertices have exactly $2n-3$ edges, a segment maximal outerplanar graph may be realized with far fewer segments. For example, the segment maximal outerplanar graph in Fig. 1 has $p=n=m=9$. This is possible because a segment can participate in arbitrarily many intersection points and circuits, while a graph edge is incident to exactly two vertices and two faces. See (Brévilliers et al. 2007; Brimkov 2013; Brimkov et al. 2011, 2012; de Castro et al. 2002; Chan and Chen 2010; Francis et al. 2012; Kára and Kratochvíl 2006; Rappaport et al. 1990) and the bibliographies therein for other applications of computing p and c, as well as for techniques and results on other problems defined on segment sets and on graphs constructed through segment sets.

Fig. 1

A segment maximal outerplanar graph with $m(M)=9$, $p(M)=9$, $c(M)=7$, $n(M)=9$, and $e(M)=15$

This paper is organized as follows. In the next section, we give some preliminary definitions and results. In Sect. 3, we give bounds on the number of intersections and circuits for various families of segment sets. We end with some final remarks and directions for future work in Sect. 4.

2 Preliminaries

A cut vertex of a graph G is a vertex whose deletion increases the number of connected components of G. A biconnected component or block of G is a maximal subgraph of G that has no cut vertices. An isomorphism between graphs $G_1$ and $G_2$ will be denoted by $G_1\simeq G_2$. Given a vertex v of G, $G-v$ will denote G with v removed, along with all edges incident to v. A vertex of G is a leaf if it has a single neighbor in G. $K_n$ denotes the complete graph on n vertices.

Let M be a set of segments and s be a segment of M with endpoints a and b. Let $a'$ be the first intersection point in s encountered when moving along s in a straight line from a to b in M, and $b'$ be the last intersection point encountered (note it is possible that $a'=a$ and $b'=b$). Trimming s is the operation of replacing s by a segment $s'$ with endpoints $a'$ and $b'$; if s has fewer than two intersection points, then trimming s means deleting s. Trimming M means repeatedly trimming the segments in M until further trimming yields no difference. Note that it may be possible to trim a segment, then trim another segment, and then trim the first segment again. See Fig. 2 for an illustration of trimming.

Fig. 2

Left: Set of segments M. Middle: Trimming every segment of M once. Right: Trimming M

We end this section with some preliminary observations about segment sets.

Proposition 1

For any nontrivial connected segment set M, there are at least two segments $s_a$ and $s_b$ in M such that $M\backslash s_a$ and $M\backslash s_b$ are connected.

Proof

Let H be a graph that has a vertex for each segment in M, and where two vertices are adjacent whenever the corresponding segments intersect in M.

Let $s_x$ and $s_y$ be any two vertices of H, and x and y be non-intersection points respectively belonging to the segments $s_x$ and $s_y$ in M. Since M is connected, there is a path $x, p_1,\ldots , p_k, y$ between x and y, where $p_1,\ldots ,p_k$ are parts of segments (or entire segments) of M. In particular, let $p_t\subseteq s_{i_t}$ for $1\le t\le k$ (where $s_{i_1}=s_x$ and $s_{i_k}=s_y$). By construction of H, for $1\le t\le k-1$, $s_{i_t}$ is adjacent to $s_{i_{t+1}}$ in H. Thus, the path $x, p_1,\ldots , p_k, y$ in M corresponds to a path $s_x, s_{i_1},\ldots , s_{i_k}, s_y$ in H, so H is connected.

Since any connected graph with at least two vertices has at least two non-cut vertices, H has two non-cut vertices $s_a$ and $s_b$. We claim that $M\backslash s_a$ and $M\backslash s_b$ are connected. To see why, let x and y be any two points in $M\backslash s_a$. If x and y belong to the same segment, clearly there is a path between them. Otherwise, let $s_x$ and $s_y$ respectively be segments containing x and y. Since $s_a$ is a non-cut vertex of H, $H-s_a$ is connected. Let $s_x,s_{i_1},\ldots ,s_{i_k},s_y$ be a simple path between $s_x$ and $s_y$ in $H-s_a$. By construction of H, segments $s_x$ and $s_{i_1}$ intersect in M; thus, there is a path between x and every point in $s_{i_1}$. Similarly, segments $s_{i_t}$ and $s_{i_{t+1}}$ intersect in M for $1\le t\le k-1$, and $s_{i_k}$ intersects $s_y$, so there is a path between x and y in $M\backslash s_a$. Thus, $M\backslash s_a$ is connected; similarly, $M\backslash s_b$ is connected. $\square$

Corollary 1

Any nontrivial segment tree M contains at least two segments $s_a$ and $s_b$ such that $M\backslash s_a$ and $M\backslash s_b$ are connected, and such that $s_a$ and $s_b$ each contain a single intersection point.

Proof

By Proposition 1, there are two segments $s_a$ and $s_b$ such that $M\backslash s_a$ and $M\backslash s_b$ are connected; we claim that each of these segments contains a single intersection point. Indeed, since M is a segment tree and is therefore connected, $s_a$ and $s_b$ must each contain at least one intersection point. Suppose for contradiction that $s_a$ contains two (or more) intersection points x and y. Since M is a segment tree, there is only one path, namely along $s_a$, between the segments that intersect $s_a$ at x and the segments that intersect $s_a$ at y. Then, there will be no path between these segments in $M\backslash s_a$, a contradiction. $\square$

3 Bounds on p and c

In this section, we derive tight bounds on the number of intersection points p and circuits c in certain families of segment sets as a function of the number of segments m.

3.1 Segment Halin graphs

A Halin graph is a graph that can be obtained by starting from a tree with no vertices of degree two that is embedded in the plane, and connecting the leaves of this tree in a cycle according to their clockwise ordering specified by the embedding. Halin graphs have a unique embedding up to the choice of which face is the outer face. A segment Halin graph is a set of segments M satisfying the following two properties: (1) $G_M$ is a Halin graph; (2) in the embedding of $G_M$ induced by M, the edges of the outer face constitute the cycle used in the construction of $G_M$. See (Cornuéjols et al. 1983; Eppstein 2016; Horton and Parker 1995; Sysło and Proskurowski 1983) for some applications and algorithmic aspects of Halin graphs.

Theorem 3

Let M be a segment Halin graph. Then

$$\begin{aligned} p(M)\ge \left\lceil \frac{m(M)+2}{2}\right\rceil ,\\c(M)\ge \left\lceil \frac{m(M)+3}{3}\right\rceil , \end{aligned}$$

and these bounds are tight.

Proof

Halin graphs do not have any leaves, so for any segment Halin graph M, $J\subset P$, and hence $p(M)=n(M)$. Furthermore, for any Halin graph G, $|E(G)|=|V(G)|-1+\ell (G)$, where $\ell (G)$ is the number of leaves of the tree used in the construction of G. Thus for any segment Halin graph M, $e(M)\le 2(p(M)-1)$, so

$$\begin{aligned} p(M)\ge \frac{e(M)+2}{2}\ge \frac{m(M)+2}{2}. \end{aligned}$$

Since m(M) is an integer, this bound can be tightened to $p(M)\ge \left\lceil \frac{m(M)+2}{2}\right\rceil$. This bound holds with equality when m is even and $m\ge 6$ for the set of segments formed by the edges of a straight-line noncollinear embedding of a wheel graph on $\frac{m}{2}+1$ vertices; see Fig. 3, left. When m is odd and $m\ge 7$, equality can be achieved by a similar construction, shown in Fig. 3, right. Since there are no segment Halin graphs with fewer than six segments, the bound on p(M) is tight for all m.

Fig. 3

Constructions demonstrating the tightness of the lower bound on p(M) for segment Halin graphs. On the left, $m(M)=12$; on the right, $m(M)=13$

Let M be a segment Halin graph, T be the tree used in the construction of $G_M$, and $\ell (T)$ be the number of leaves of T. Then, $|E(G_M)|=|E(T)|+|E(G_M)\backslash E(T)|=|V(T)|-1+\ell (T)$. Moreover, since by definition T has no degree 2 vertices, its $\ell (T)$ leaves have degree 1, and its $|V(T)|-\ell (T)$ non-leaf vertices have degree at least 3. Then,

$$\begin{aligned} 2(|V(T)|-1)= & {} 2|E(T)|=\sum _{v\in V(T)}deg(v)\\\ge & {} \ell (T)+3(|V(T)|-\ell (T))= 3|V(T)|-2\ell (T). \end{aligned}$$

Solving for |V(T)|, we obtain $|V(T)|\le 2\ell (T)-2$. Moreover, the number of bounded faces of $G_M$ equals $\ell (T)$; thus, combining the inequalities above, we have

$$\begin{aligned} m(M)\le |E(G_M)|\le 3\ell (T)-3=3c(M)-3. \end{aligned}$$

Solving for c(M), we obtain $c(M)\ge \frac{m(M)+3}{3}$, and since m(M) is an integer, this bound can be tightened to $c(M)\ge \left\lceil \frac{m(M)+3}{3}\right\rceil$.

The bound on c(M) holds with equality when $m \equiv 0\ (\text {mod}\ 3)$ for the following construction, shown in Fig. 4, left: let $t=\frac{m}{3}+1$ and draw a regular t-gon S with intersection points $p_1,\ldots ,p_{t}$ in clockwise order, and a larger, dilated concentric copy of S with intersection points $p_1',\ldots ,p_{t}'$ in clockwise order; delete the segments $\overline{p_1p_2}$, $\overline{p_2p_3}$, $\overline{p_3p_4}$, and add the segments $\overline{p_1p_2'}$, $\overline{p_4p_3'}$, $\overline{p_1p_1'}$, and $\overline{p_kp_k'}$ for $4\le k\le t$. Similar constructions can be used in the cases when $m \equiv 2\ (\text {mod}\ 3)$ and $m \equiv 1\ (\text {mod}\ 3)$; see Fig. 4, center, and Fig. 4, right, respectively. Thus, the bound on c(M) is tight for all m. $\square$

Fig. 4

Constructions demonstrating the tightness of the lower bound on c(M) for segment Halin graphs. On the left, $m(M)=21$; in the center, $m(M)=20$; on the right, $m(M)=19$

Theorem 4

Let M be a segment Halin graph. Then

$$\begin{aligned} p(M)\le & {} 3m(M)-11,\\ c(M)\le & {} 2m(M)-6, \end{aligned}$$

and these bounds are tight.

Proof

Let T be the tree used in the construction of $G_M$, let ${\mathcal {C}}$ be the cycle used in the construction of $G_M$ equipped with the embedding induced by M, and let $\ell (T)=|{\mathcal {C}}|$ denote the number of leaves of T (equivalently, the order of ${\mathcal {C}}$). We will call vertices of ${\mathcal {C}}$ convex, straight, and concave if their interior angle with respect to the embedding of ${\mathcal {C}}$ is respectively less than $\pi$, equal to $\pi$, and greater than $\pi$. Given a polygon with k vertices, the sum of the interior angles of the vertices is $(k-2)\pi$. Thus, the polygon must contain at least 3 convex vertices, since if at most 2 of its k vertices are convex, the sum of the interior degrees of the vertices would be greater than $(k-2)\pi$, a contradiction.

We will first show that there are at least 3 segments in M which belong exclusively to ${\mathcal {C}}$ and not to T. If a segment of M belongs to both ${\mathcal {C}}$ and T, it must pass between ${\mathcal {C}}$ and T at a concave vertex of ${\mathcal {C}}$. Moreover, since only leaves of T touch ${\mathcal {C}}$, at most one of the segments that meet at a concave vertex can pass from ${\mathcal {C}}$ to T at that vertex. Since ${\mathcal {C}}$ (equipped with its embedding induced by M) is a polygon, ${\mathcal {C}}$ must contain at least 3 convex vertices. Suppose ${\mathcal {C}}$ contains r straight vertices. Then, the number of non-straight vertices of ${\mathcal {C}}$ is $|{\mathcal {C}}|-r$, and hence the number of segments that make up ${\mathcal {C}}$ is $|{\mathcal {C}}|-r$. Since at least 3 of the vertices of ${\mathcal {C}}$ are convex, at most $|{\mathcal {C}}|-r-3$ of the vertices of ${\mathcal {C}}$ are concave, so there are at most $|{\mathcal {C}}|-r-3$ places where a segment can pass from T to ${\mathcal {C}}$. Then, at most $|{\mathcal {C}}|-r-3$ of the segments of ${\mathcal {C}}$ pass into T. Every segment that does not pass into T is a segment that is contained entirely in ${\mathcal {C}}$. Thus, at least 3 segments belong to ${\mathcal {C}}$ but not T, so

$$\begin{aligned} m(T)\le m(M)-3. \end{aligned}$$

(1)

Using the inequality in (1) and the fact that Halin graphs have no leaves, we have

$$\begin{aligned} p(M)=n(M)=n(T)\le & {} p(T)+j(T) \\\le & {} m(T)-1+2m(T)=3m(T)-1\\\le & {} 3(m(M)-3)-1. \end{aligned}$$

We show that at least one of the three inequalities above must be strict. Suppose for contradiction that $p(M)=3m(M)-10$. Then, all of the following hold:

• (1) $n(M)=p(T)+j(T)$,

• (2) $p(T)+j(T)=3m(T)-1$,

• (3) $m(T)=m(M)-3$.

Equality (3) implies that exactly 3 segments of M are exclusively in ${\mathcal {C}}$ and not in T. Hence, $|{\mathcal {C}}|-r-3$ of the segments of ${\mathcal {C}}$ must pass into T. Since segments can only pass between ${\mathcal {C}}$ and T at a concave vertex of ${\mathcal {C}}$, and since at most one of the segments that meet at a concave vertex can pass from ${\mathcal {C}}$ to T at that vertex, it follows that $|{\mathcal {C}}|-r-3$ of the non-straight vertices of ${\mathcal {C}}$ must be concave. Thus, there are exactly 3 convex vertices in ${\mathcal {C}}$.

Let the convex vertices of ${\mathcal {C}}$ be $a_1,a_2,a_3$, and let $s_i$ be the segment of T which has an endpoint at $a_i$, $1\le i\le 3$. Let $A_{12}$ be the path in ${\mathcal {C}}$ between $a_1$ and $a_2$ that does not pass through $a_3$; define $A_{13}$ and $A_{23}$ analogously. Equalities (1) and (2) imply that no intersection point of T is also an endpoint of a segment of T, that no three segments of T intersect in the same point, and that both endpoints of each segment of T are leaves of T and touch ${\mathcal {C}}$. Since all vertices on $A_{12}$ and $A_{13}$ are concave or straight, $s_1$ cannot have its other endpoint on $A_{12}$ or $A_{13}$; thus, it must be in $A_{23}$. Similarly, $s_2$ must have its other endpoint in $A_{13}$. Thus, the segments $s_1$ and $s_2$ intersect in a point x in the interior of ${\mathcal {C}}$. Moreover, $s_3$ must have its other endpoint in $A_{12}$, and must therefore intersect $s_1$ and $s_2$; see Fig. 5, left, for an illustration. However, if $s_3$ does not pass through x, then the segments $s_1,s_2,s_3$ form a triangle in the interior of ${\mathcal {C}}$; this triangle must be part of T, contradicting the fact that T is a tree. On the other hand, if $s_3$ passes through x, this contradicts the fact that no three segments of T intersect in the same point. Thus, (1), (2), and (3) cannot all hold at the same time, so $p(M)<3m(M)-10$. Since p(M) is an integer, it follows that $p(M)\le 3m(M)-11$.

The number of bounded faces of $G_M$ equals $\ell (T)$; thus, again using the inequality (1), we have $c(M)=\ell (T)\le 2m(T)\le 2(m(M)-3)$. The upper bounds on p and c are tight for all $m\ge 6$ for the family of segment Halin graphs shown in Fig. 5, right. $\square$

Fig. 5

Left: The outer face of a Halin graph with exactly 3 convex points. Right: Construction demonstrating the tightness of the upper bounds on p(M) and c(M) for segment Halin graphs

3.2 Segment cactus graphs

A graph G is called a cactus graph if any two cycles of G have at most one vertex in common. Every edge of a cactus graph belongs to at most one cycle, and the biconnected components of a cactus graph are either cycles or single edges. By definition, two circuits of a segment cactus graph can have at most one vertex in common, i.e., they cannot share a portion of a segment different from a point. Properties of cactus graphs have been studied with some applications in mind; for example, cactus graphs arise in the design of telecommunication systems, material handling networks, and local area networks (cf. Ben-Moshe et al. 2012; Brimkov and Hicks 2017; Harary and Uhlenbeck 1953; Husimi 1950; Kariv and Hakimi 1979; Koontz 1980 and the bibliographies therein).

Proposition 2

A connected segment cactus graph M with $c \ge 1$ circuits contains at least two segments $s_1$ and $s_2$, such that for $i\in \{1,2\}$,

(A):

$s_i$ belongs to a single circuit segment set $S_i$,

(B):

the connected components of $M\backslash s_i$ which do not contain segments of $S_i$ are segment trees.

Proof

If $c=1$, every segment in the single circuit segment set of M satisfies properties (A) and (B); thus, assume henceforth that $c \ge 2$.

Let $Q=\{s_1,\ldots ,s_q\}$ be a maximal set of segments of M such that for $1\le i\le q$, $s_i$ does not belong to any circuit segment set of M, and $s_i$ is a segment whose deletion does not disconnect $M\backslash \{s_1,\ldots ,s_{i-1}\}$. Let $M'=M\backslash Q$. By construction, M and $M'$ have the same circuit segment sets; moreover, the connected components of $M\backslash M'$ (i.e. of Q) are segment trees. Hence, for any segment $s\in M'$, the connected components of $M\backslash s$ which do not contain segments of $M'$ are segment trees. Let $M''$ be the set of segments obtained by trimming $M'$ (in fact, $M''$ is identical to the set of segments obtained by trimming M). Note that M, $M'$, and $M''$ have the same circuits.

The graph $G_{M''}$ has no leaves, since a leaf of $G_{M''}$ would have to be an endpoint of a segment in $M''$, and all endpoints of segments in $M''$ are also intersection points. Thus, all outer blocks of $G_{M''}$ (i.e., biconnected components with a single cut vertex) are cycles. Since $c\ge 2$ and since M and $M''$ have the same circuits, it follows that $G_{M''}$ has at least two cycles; thus, $G_{M''}$ has at least two outer blocks which are cycles, say $C_1$ and $C_2$. Let $S_1$ and $S_2$ be the circuit segment sets in M corresponding to $C_1$ and $C_2$, respectively. For $i\in \{1,2\}$, exactly two edges of $C_i$ in $G_{M''}$ are incident to the cut vertex $v_i$ of $C_i$; thus, in M, $v_i$ corresponds to an intersection point of at most two segments of $S_i$. Since $S_i$ contains at least three segments, there is a segment $s_i\in S_i$ which does not contain $v_i$ as an intersection point in M. Then, since $C_i$ is an outer cycle block, $s_i$ does not belong to any other circuit segment set of M, i.e., $s_i$ satisfies property A). Furthermore, the connected components of $M\backslash s_i$ which do not contain segments of $S_i$ also do not contain segments of $M'$. However, as shown above, the connected components of $M\backslash s_i$ which do not contain segments of $M'$ are segment trees. Thus, $s_i$ satisfies property B). $\square$

Theorem 5

Let M be a segment cactus graph. Then

$$\begin{aligned} p(M)\le & {} 2(m(M)-k_1(M))-3k_2(M), \end{aligned}$$

(2)

$$\begin{aligned} c(M)\le & {} (m(M)-k_1(M))-2k_2(M), \end{aligned}$$

(3)

and these bounds are tight.

Proof

If M is a segment forest, then $p\le 2p-k_2\le 2(m-k_1-k_2)-k_2=2(m-k_1)-3k_2$, where the first inequality follows from Observation 1 (part 6.) and the second inequality follows from Observation 2 (part 2.); this establishes the upper bound in (2). Likewise, if M is a segment forest, then the upper bound in (3) follows from Observation 1 (part 5.) and the fact that $c=0$. Thus, it remains to be shown that the upper bounds in (2) and (3) hold for the case when the segment cactus graph is not a segment forest, i.e., when $c \ge 1$, and hence $m\ge 3$. We will proceed by induction on m. Both inequalities clearly hold for $m=3$. Assume the inequalities hold for some $m \ge 3$ and let M be a segment cactus graph with $m+1$ segments.

By Proposition 2, M contains a segment $s_1$ which belongs to a single circuit segment set $S_1$ of a connected component $M_1$ of M, such that the connected components of $M_1\backslash s_1$ which do not contain segments of $S_1$ are segment trees. If $M_1\backslash s_1$ does not have any connected components which do not contain segments of $S_1$, let $s_*=s_1$. Note that in this case, deleting $s_*$ from M decreases the number of intersection points by at most two, and the number of circuits by one. If $M_1\backslash s_1$ has at least one connected component T which does not contain segments of $S_1$, then T is a segment tree which can only intersect $s_1$ in a single point, since otherwise $s_1$ would be part of at least two circuits. If T consists of a single segment, let $s_*$ be that segment. If T contains at least two segments, then by Corollary 1, T contains two segments $s_a$ and $s_b$, each having a single intersection point, such that removing either one of them from T does not disconnect T. If neither $s_a$ nor $s_b$ intersect $s_1$, let $s_*=s_a$. If exactly one of $s_a$ and $s_b$ intersects $s_1$, let $s_*$ be the segment among $s_a$ and $s_b$ which does not intersect $s_1$. If both $s_a$ and $s_b$ intersect $s_1$, then $s_1$, $s_a$, and $s_b$ must all intersect in the same point; in this case, let $s_*=s_1$. In each of these cases, deleting $s_*$ from M decreases the number of intersection points by at most one and does not affect the number of circuits.

Thus, the segment cactus graph $M\backslash s_*$ has m segments, $p-i$ intersection points for some $i\in \{0,1,2\}$, and $c-t$ circuits for some $t\in \{0,1\}$. By the induction hypothesis, $p-i \le 2(m-k_1)-3k_2$. Then, for the segment cactus graph M with $m+1$ segments and p intersections, we obtain $p \le 2(m-k_1)-3k_2+i\le 2(m-k_1)-3k_2+2=2(m+1-k_1)-3k_2$. Similarly, by the induction hypothesis, $c-t \le (m-k_1)-2k_2$. Then, for the segment cactus graph M with $m+1$ segments and c circuits we obtain $c \le (m-k_1)-2k_2+t\le (m-k_1)-2k_2+1=(m+1-k_1)-2k_2$. This concludes the inductive step and establishes the inequalities. The inequalities in (2) and (3) hold with equality for all $m\ge 1$ for the construction shown in Fig. 6. $\square$

Fig. 6

Construction demonstrating the tightness of the upper bounds on p(M) and c(M) for segment cactus graphs; in this example, $m(M)=9$, $p(M)=15$, and $c(M)=7$

Since a segment forest is a segment cactus graph, $p\ge k_2$ and $c\ge 0$ are tight lower bounds for segment cactus graphs.

3.3 Segment $K_3$-free graphs

A $K_3$-free graph² is a graph which has no subgraph isomorphic to $K_3$.

Theorem 6

Let M be a segment $K_3$-free graph. Then

$$\begin{aligned}&p(M)\le {m(M)\atopwithdelims ()2}-(m(M)-2),\\&c(M)\le {m(M)-2\atopwithdelims ()2}, \end{aligned}$$

and these bounds are tight.

Proof

Given a segment set M, let t(M) denote the number of $K_3$ subgraphs of $G_M$, let $A(M)=p(M)-t(M)$, and let $B(M)=c(M)-t(M)$. When there is no scope for confusion, dependence on M will be omitted. We will refer to the circuits of M which correspond to $K_3$-subgraphs of $G_M$ as triangle circuits. Let M be an arbitrary segment $K_3$-free graph with m segments. Let $M_0$ be obtained from M by extending each segment s of M which has an endpoint that is also an intersection point by a small distance in the direction of that endpoint so that the endpoint is no longer an intersection point, but s does not intersect any new segment. Note that $M_0$ is also a segment $K_3$-free graph (since $G_{M_0}$ is obtained by adding some leaves to $G_{M}$, which cannot create a $K_3$ subgraph), and that $p(M)=p(M_0)$ and $c(M)=c(M_0)$. Let the segments of $M_0$ be $s_1,\ldots ,s_m$. We will transform $M_{i-1}$, $i\ge 1$, into $M_{i}$ by perturbing $s_i$ as follows.

First, translate $s_i$ by a small distance so that none of its intersection points are shared with more than one other segment, and so that $s_i$ does not intersect any segments that it did not previously intersect. Since none of the endpoints in $M_i$ are intersection points, this can be done by choosing a small enough translation distance (which is also small enough that no endpoints become intersection points after the translation). For each intersection point of $s_i$ that was shared with more than one other segment before the translation, the number of new intersection points that are created as a result of the translation is one more than the number of new triangle circuits created (see Fig. 7 for an illustration). Each existing triangle circuit which intersects $s_i$ in a side or a point either remains a triangle circuit or is turned into non-triangle circuit through the translation. However, non-triangle circuits cannot disappear or be turned into triangle circuits through the translation, because doing so would require segments which did not previously intersect to intersect after the translation. Thus, B does not decrease after the translation; moreover, since p increases at least as much as t after the translation, A also does not decrease.

Fig. 7

The bold segment is translated by a small distance so that none of its intersection points share more than one other segment. The number of triangle circuits created by the translation (shaded dark) is no more than the number of intersection points created; some triangle circuits become non-triangle circuits (shaded light), but no non-triangle circuits disappear

Next, rotate $s_i$ by a small (possibly zero) degree so that it is not parallel to any other segment in $M_i$. The degree can be chosen small enough so that each intersection point of $s_i$ remains an intersection point between the same two segments it was previously an intersection point between (note that the endpoints are not intersection points, so no intersection points will disappear if the degree of rotation is small enough). Thus, the topology of neither the circuits nor the intersection points is affected by this rotation, so A and B do not change.

Next, extend $s_i$ from one endpoint until it intersects another segment, if this is possible. If extending $s_i$ from that endpoint never causes it to intersect another segment, simply extend $s_i$ from that endpoint by a sufficiently large distance (as described further below). If extending $s_i$ from that endpoint does cause it to intersect another segment and if the extended endpoint of $s_i$ intersects the new segment at an already-existing intersection point, translate $s_i$ by a small distance so that all of the previous intersection points and circuits (and their topologies) are preserved, but the extended endpoint of $s_i$ intersects the new segment in a point that was not previously an intersection point. As discussed previously, no non-triangle circuits disappear as a result of such a translation, if one is necessary. If the extension does not split any circuit into two circuits, then B has not changed, t has not changed, and p has increased by one. If this extension does split a circuit into two circuits, then at most one of these two circuits is a triangle, since splitting a circuit into two triangle circuits requires at least one of the two intersection points of $s_i$ with the circuit to be a point where 3 segments meet (this is avoided by the translations). Thus, in either case, p increases at least as much as t, so A does not decrease. Moreover, regardless of whether the circuit that is split by $s_i$ was a triangle or a non-triangle, B cannot decrease, since in either case at least one new non-triangle circuit is created and at most one non-triangle circuit disappears. Repeat this extension with both endpoints of $s_i$ until no new segments can be crossed, and then extend both endpoints by a sufficiently large distance so that all future extensions of segments will be able to intersect $s_i$. Call the resulting set of segments $M_{i+1}$. Since at each step of the perturbation, A and B either increase or remain unchanged, it follows that $A(M_i)\le A(M_{i+1})$ and $B(M_i)\le B(M_{i+1})$.

By repeating the same perturbation with all segments, we obtain a sequence of segment sets $M_0,\ldots ,M_m$ such that $A(M_0)\le \ldots \le A(M_m)$ and $B(M_0)\le \ldots \le B(M_m)$. In $M_m$, no segments are parallel, and no intersection point is shared by more than two segments; moreover, since the segments are long enough, each segment intersects every other segment. If each segment of $M_m$ is extended to a line, we obtain a set of lines ${\mathcal {L}}$ in general position; moreover, $A({\mathcal {L}})=A(M_m)$ and $B({\mathcal {L}})=B(M_m)$ since no new circuits or intersection points can be created by extending the segments. It is well-known that for a set of lines ${\mathcal {L}}$ in general position, $p({\mathcal {L}})=\left( {\begin{array}{c}m\\ 2\end{array}}\right)$ and $t({\mathcal {L}})\ge m-2$. Hence, since $t(M_0)=0$, we have

$$\begin{aligned} p(M)= & {} p(M_0)-t(M_0)=A(M_0)\le A(M_m)\\= & {} A({\mathcal {L}})=p({\mathcal {L}})-t({\mathcal {L}})\le \left( {\begin{array}{c}m\\ 2\end{array}}\right) -(m-2). \end{aligned}$$

It is also well-known that the number of regions formed by a set of m lines in general position is $\frac{m^2+m+2}{2}$ (this is known as the sequence of central polygonal numbers); this count includes 2m unbounded regions, so $c({\mathcal {L}})=\frac{m^2+m+2}{2}-2m$. Then,

$$\begin{aligned} c(M)= & {} c(M_0)-t(M_0)=B(M_0)\\\le & {} B(M_m)\le B({\mathcal {L}})=c({\mathcal {L}})-t({\mathcal {L}})\\\le & {} \frac{m^2+m+2}{2}-2m-(m-2). \end{aligned}$$

Since M was arbitrary, it follows that for any segment $K_3$-free graph, $p\le \left( {\begin{array}{c}m\\ 2\end{array}}\right) -(m-2)$ and $c\le \frac{m^2+m+2}{2}-2m-(m-2)=\left( {\begin{array}{c}m-2\\ 2\end{array}}\right)$. These bounds are tight for the following construction. Start with vertical parallel segments $r_0$ and $\ell _0$ which are long enough for future segments to intersect. Let $r_1$ be a segment crossing both $r_0$ and $\ell _0$ at an angle to the right. Then, for $i\ge 1$, we iteratively add segments $\ell _i$ and $r_{i+1}$ as follows. After a segment $r_i$ is added, find the intersection of $r_i$ and $r_{i-1}$, move down along $r_{i-1}$ a short distance, and place one endpoint of the segment $\ell _i$ there. From this endpoint, $\ell _i$ continues downward and to the left, at such an angle that it intersects every line already present, except for $r_i$. After a segment $\ell _i$ is added, find the intersection of $\ell _i$ and $\ell _{i-1}$, move down along $\ell _{i-1}$ a short distance, and place one endpoint of the segment $r_{i+1}$ there. From this endpoint, $r_{i+1}$ continues downward and to the right, at such an angle that it intersects every line already present, except for $\ell _i$. Newly added segments are long enough for all future segments to intersect; see Fig. 8 for an illustration. There are two intersection points and zero circuits among $r_0$, $\ell _0$, and $r_1$; then, beginning with the fourth segment, each added segment intersects all-but-one of the existing segments. Thus, the total number of intersection points in this construction is $2+\sum _{i=4}^{m}(i-2)={m\atopwithdelims ()2}-(m-2)$, and the total number of circuits is $\sum _{i=4}^{m}(i-3)={m-2\atopwithdelims ()2}$. $\square$

Fig. 8

Construction demonstrating the tightness of the upper bound on p(M) for segment $K_3$-free graphs; in this example, $m=8$ and $p=22$

Since a segment forest is a segment $K_3$-free graph, $p\ge k_2$ and $c\ge 0$ are tight lower bounds for general segment $K_3$-free graphs. A better lower bound can be derived for a segment $K_3$-free graph M which has been trimmed (i.e., the corresponding graph $G_M$ has no leaves). In this case, $p= n\ge \frac{e+4}{2}\ge \frac{m+4}{2}$, where the first inequality follows from the fact that for any planar $K_3$-free graph G, $|E(G)|\le 2(|V(G)|-2)$. This bound is tight, e.g., for a noncollinear straight-line embedding of the complete bipartite graph with parts of size 2 and $n-2$.

3.4 Segment maximal planar graphs

A graph is maximal planar if it is planar and adding any edge causes it to no longer be planar. Every face of a maximal planar graph (in any planar embedding) is a triangle.

Proposition 3

Let M be a segment maximal planar graph. Then

$$\begin{aligned} p(M)\ge \left\lceil \frac{m(M)+6}{3}\right\rceil ,\\c(M)\ge \left\lceil \frac{2m(M)-3}{3}\right\rceil , \end{aligned}$$

and these bounds are tight. Moreover, there exist segment maximal planar graphs with $p=\theta (m^2)$ and $c=\theta (m^2)$.

Proof

Maximal planar graphs do not have any leaves, so for segment maximal planar graphs, $J\subset P$, and hence $p=n$. For any maximal planar graph G, $|E(G)|=3|V(G)|-6$. Thus, $p=\frac{e+6}{3}\ge \frac{m+6}{3}$ and since p is an integer, this bound can be tightened to $p\ge \lceil \frac{m+6}{3}\rceil$. By Euler’s formula and by the previous inequality,

$$\begin{aligned} c=1-n+e=1-n+(3n-6)=2n-5=2p-5\ge 2\left( \frac{m+6}{3}\right) -5=\frac{2m-3}{3}, \end{aligned}$$

and since c is an integer, this bound can be tightened to $c\ge \lceil \frac{2m-3}{3}\rceil$. The bounds on p and c hold with equality for any segment set obtained from a straight-line plane embedding of a maximal planar graph in which the edges are drawn as non-collinear segments. The set of segments obtained by triangulating an equilateral triangle with $x\ge 0$ segments parallel to each side, and connecting an external point to each intersection point on each side of the boundary of the triangle as in Fig. 9, has $m=6x+9$ segments, and hence $p=\frac{(x+3)(x+2)}{2}+3=\frac{m^2}{72}+\frac{m}{6}+\frac{27}{8}=\theta (m^2)$ and $c=(x+1)^2+3(x+2)=\frac{m^2}{36}+\frac{m}{3}+\frac{7}{4}=\theta (m^2)$. $\square$

Fig. 9

Construction demonstrating the tightness of the asymptotic upper bound on p(M) and c(M) for segment maximal planar graphs

3.5 Buffon segments

A set of segments $M=M(m,\ell )$ is called a Buffon set³ if it is produced by m segments of length $\ell$ randomly placed in the unit square; dependence on m and $\ell$ will be omitted when it is clear from the context. We will assume the centers and angles of the segments are chosen uniformly at random. In this section, we investigate the expected number of intersection points in a Buffon set of segments as a function of m and $\ell$, along with other structural properties. Since the segments in a Buffon set are placed inside a unit square, throughout this section we will assume that $\ell <1$ unless otherwise stated. If this assumption is lifted, it can easily be shown that “$\ell$” in the statements of Proposition 4, Theorem 7, and Theorem 8 can be replaced with “$\min (\ell ,1)$”.

Proposition 4

Let M be a Buffon set of segments. The expected number of distinct subsets of M of t segments which mutually intersect is $O(m^t\ell ^{2t-2})$.

Proof

Let $s_1,\ldots ,s_t$ be segments in M; let X be the event that $s_1,\ldots ,s_t$ mutually intersect, and let Y be the event that the centers of $s_{2}, \dots , s_{t}$ are within distance $\ell$ of the center of $s_{1}$. If the center of some $s_i$, $2\le i\le t$, is not within distance $\ell$ of the center of $s_1$, then $s_1,\ldots ,s_t$ cannot mutually intersect. Thus, X implies Y, and $Pr[X]\le Pr[Y]$. Moreover, $Pr[Y] \le (\pi \ell ^2)^{t-1}$, since this is the probability that the centers of $s_2,\ldots ,s_t$ lie in a disk with radius $\ell$ centered at the center of $s_1$. Thus, $Pr[X]=O(\ell ^{2t-2})$. The number of distinct sets of t segments which mutually intersect is equal to $\sum _{T\subset M,\, |T|=t} X_T$, where $X_T$ is the indicator random variable for the event that the segments in T mutually intersect. By linearity of expectation and the fact that $E[X_T]=O(\ell ^{2t-2})$, the expected number of distinct sets of t segments which mutually intersect is $\sum _{T\subset M,\, |T|=t}E[X_T] = O(m^t\ell ^{2t-2})$. $\square$

Theorem 7

Let M be a Buffon set of segments. Then, $E[p(M)]=\theta (m^2 \ell ^2)$.

Proof

Let X be the event that two segments $s_{1}, s_{2}$ of length $\ell$ intersect, let Y be the event that the distance between the centers of $s_1$ and $s_2$ is at most $\ell / 2$, and let Z be the event that the distance between the centers of $s_1$ and $s_2$ is exactly $\ell / 2$. Let $p_1=Pr[X]$, $p_2=Pr[X \cap Y]$, $p_3=Pr[X|Y]$, $p_4=Pr[Y]$, and $p_5=Pr[X|Z]$. Clearly $p_1\ge p_2$, and by definition of conditional probability, $p_2 = p_3 p_4$. Moreover, $p_3 \ge p_5$ since the probability that two segments intersect decreases with the distance between their centers. Also, note that $p_5$ is a constant independent of $\ell$, since the probability that two segments of length $\ell$ intersect given that their centers are $\ell /2$ apart is equal to the probability that two segments of length $x\ell$ intersect, given that their centers are $x\ell /2$ apart, for any $x > 0$ (including $x=1/\ell$). Finally, in order for event Y to occur, the center of $s_2$ would have to lie in a disk of radius $\ell /2$ centered at the center of $s_1$; since at least a quarter of such a disk intersects the unit square (this happens when the center of $s_1$ is in a corner of the unit square), it follows that $p_4 \ge \frac{1}{4} \pi (\ell / 2)^2$. Thus, $p_1 \ge p_2\ge p_4p_5\ge \frac{p_5 \pi }{16} \ell ^2 = \Omega (\ell ^2)$.

Now, $p(M)= \sum _{\{s_1,s_2\}\subset M} X_{\{s_1,s_2\}}$, where $X_{\{s_1,s_2\}}$ is the indicator random variable for the event that segments $s_1$ and $s_2$ intersect. From the above argument, $E[X_{\{s_1,s_2\}}]=\Omega (\ell ^2)$. By linearity of expectation,

$$\begin{aligned} E[p(M)]=\sum _{\{s_1,s_2\}\subset M}E[X_{\{s_1,s_2\}}]= \Omega (m^2 \ell ^2). \end{aligned}$$

Moreover, by Proposition 4, $E[p(M)]=O(m^2\ell ^2)$; thus, $E[p(M)]=\theta (m^2\ell ^2)$. $\square$

Corollary 2

Let M be a Buffon set of segments of length at most $\left( \frac{a}{m}\right) ^{3/4}$, for any constant $a>0$. Then, the expected number of $K_3$ subgraphs of $G_M$ is O(1).

Proof

Each $K_3$ subgraph in $G_M$ corresponds to a distinct triple of mutually intersecting segments in M (but not vice versa). By Proposition 4, the expected number of triples of mutually intersecting segments in M is $O(m^3\ell ^{4})$. Since $\ell \le \left( \frac{a}{m}\right) ^{3/4}$ and a is a constant independent of m, it follows that the expected number of $K_3$ subgraphs in $G_M$ is O(1). $\square$

The complexity of a set of segments M is the sum of the vertices, edges, and bounded faces of $G_M$. Below we derive a bound on the expected complexity of a Buffon set of segments that is tight up to a constant factor.

Theorem 8

Let M be a Buffon set of segments. The expected complexity of M is $\theta (m^2 \ell ^2+m)$.

Proof

In a Buffon set, the expected number of points which are both endpoints of segments and intersection points is zero, and the expected number of intersection points where more than 2 segments meet is zero. Thus, in expectation, $n(M) = p(M)+j(M)=p(M)+2m(M)$, and

$$\begin{aligned} e(M)=\sum _{s\in M} (\text {number of intersection points in } s \text { plus } 1)= 2p(M)+m(M). \end{aligned}$$

Let $M_1,\ldots ,M_t$ be the connected components of M. By the argument above, in expectation, for $1\le i\le t$, $n(M_{i})=p(M_i)+2m(M_i)$ and $e(M_i)=2p(M_i)+m(M_i)$. By Euler’s formula, the expected number of faces of $M_{i}$ (including the outer face) is $(2p(M_{i})+m(M_{i}))+2-(p(M_{i})+2m(M_{i})) = p(M_{i})-m(M_{i})+2$. Counting only the bounded faces and summing over i, we have $c(M)=\sum _{i=1}^{t} (p(M_i)-m(M_i)+1)=p(M)-m(M)+t$. Thus, by linearity of expectation, the expected complexity of M is $E[n(M)]+E[e(M)]+E[c(M)]=4E[p(M)]+2m(M)+t$. Since by Theorem 7, $E[p(M)]=\theta (m^2 \ell ^2)$, and since $1\le t\le m$, it follows that the expected complexity of M is $\theta (m^2 \ell ^2+m)$. $\square$

Finally, we give necessary and sufficient conditions for a Buffon set of segments to have no intersections (i.e., for $G_M$ to be a perfect matching) with probability approaching 1 as the number of segments increases. We begin with a technical lemma.

Lemma 1

Let m and t be positive integers, $m\ge 2$, $m\ge t$, and let $x \in [0, 1/m]$. Then,

$$\begin{aligned} \prod _{i=1}^{t}(1-ix)\ge 1-\frac{t(t+1)}{2}x. \end{aligned}$$

Proof

Let $f(x) = \prod _{i=1}^{t}(1-ix)$. Then,

$$\begin{aligned} f'(x)= & {} \sum _{1\le i\le t} (-i)\prod _{j\in \{1,\ldots ,t\}\backslash \{i\}}(1-jx),\\ f''(x)= & {} \sum _{1\le i<j\le t} 2ij \prod _{k\in \{1,\ldots ,t\}\backslash \{i,j\}}(1-kx). \end{aligned}$$

By Taylor’s Theorem, $f(x) = f(0)+ f'(0) x+\frac{f''(r)}{2} x^2$, for some $r \in (0, x)$. Note that $f(0) = 1$ and $f'(0) = -\frac{t(t+1)}{2}$. Moreover, since $r< x\le 1/m$ and $k\le t\le m$, $f''(r)$ is a sum of products of nonnegative real numbers, so $f''(r)\ge 0$. Thus, $f(x)\ge 1-\frac{t(t+1)}{2}x$. $\square$

Theorem 9

Let M be a Buffon set of segments of length $\ell$. Then, as $m\rightarrow \infty$, $Pr[p(M)=0]\rightarrow 1$ if and only if $\ell =o(1/m)$.

Proof

Let the segments in M be $s_{1}, \dots , s_{m}$, and for $1\le t\le m$, let $M_t=s_1\cup \ldots \cup s_t$. If $\ell = o(\frac{1}{m})$, then $Pr[p(M)>0]=Pr[p(M)\ge 1]\le \frac{E[p(M)]}{1}\rightarrow 0$ as $m\rightarrow \infty$, where the last inequality follows from Theorem 7 and from Markov’s inequality. Thus, if $\ell = o(\frac{1}{m})$, then $Pr[p(M)=0]\rightarrow 1$ as $m \rightarrow \infty$.

Now, suppose that $\ell =\frac{\alpha }{m}$ for some $\alpha \in (0, \sqrt{1/\pi }]$. Let $X_t$ be the event that the centers of $s_{1}, \dots , s_{t-1}$ are all at least at distance $\ell$ from each other. Since $X_t$ implies that $p(M_{t-1})=0$ with probability 1, and by the definition of conditional probability, we have

$$\begin{aligned} Pr[(p(M_t)>0) \cap (p(M_{t-1})=0)]\ge & {} Pr[(p(M_t)>0) \cap X_t]\nonumber \\= & {} Pr[X_t] \,Pr[(p(M_t)>0) \,|\, X_t]. \end{aligned}$$

(4)

The probability that the center of $s_{2}$ is at least $\ell$ away from the center of $s_{1}$ is at least the area of the unit square minus the area of a disk of radius $\ell$; hence,

$$\begin{aligned} Pr[X_3]\ge 1- \pi \ell ^2. \end{aligned}$$

Similarly, the probability that the center of $s_t$ is outside the disks of radius $\ell$ around the centers of $s_1,\ldots ,s_{t-1}$ is at least $1-(t-1) \pi \ell ^2$, so

$$\begin{aligned} Pr[X_{t+1}\,|\,X_{t}] \ge 1-(t-1) \pi \ell ^2. \end{aligned}$$

Thus, by the chain rule for probabilities,

$$\begin{aligned} Pr[X_t] =\prod _{i=3}^{t}Pr[X_i\,|\,X_{i-1}]\ge \prod _{i=1}^{t-2} (1- i \pi \ell ^2) \ge 1-\frac{(t-1)(t-2)}{2}\pi \ell ^2, \end{aligned}$$

(5)

where the last inequality follows from Lemma 1. Note that since $\alpha \le \sqrt{1/\pi }$ and $\ell =\alpha /m$, it follows that $\pi \ell ^2 \le 1/m$ for all $m\ge 1$, so the conditions of Lemma 1 are satisfied.

Moreover, as shown in the proof of Theorem 7, the probability that two segments of length $\ell$ intersect is at least $\frac{p_5\pi }{16}\ell ^2$, where $p_5$ is the probability that two segments of length 1 intersect, given that their centers are distance 0.5 apart. By the same argument, if the center of $s_{t}$ is within distance $\ell /2$ of the center of some other segment $s_i$, $1\le i\le t-1$, the conditional probability that $s_{t}$ intersects $s_i$ is at least $p_5$. Thus,

$$\begin{aligned} Pr[(p(M_t)>0) \,|\, X_t] \ge (t-1)\frac{p_5\pi }{16}\ell ^2. \end{aligned}$$

(6)

Substituting (5) and (6) into (4), we obtain

$$\begin{aligned} Pr[(p(M_t)>0) \cap (p(M_{t-1})=0)] \ge \left( 1-\frac{(t-1)(t-2)}{2}\pi \ell ^2\right) (t-1)\frac{p_5\pi }{16}\ell ^2. \end{aligned}$$

The event $(p(M)>0)$ is the disjoint union of the events $(p(M_t)>0) \cap (p(M_{t-1})=0)$, $2\le t\le m$. Thus, $Pr[p(M)>0]$ can be computed as follows:

$$\begin{aligned} Pr[p(M)>0]= & {} \sum _{t = 2}^{m} Pr[(p(M_t)>0) \cap (p(M_{t-1})=0)]\\\ge & {} \frac{p_5\pi }{16}\ell ^2 \sum _{t = 1}^{m-1} t\left( 1-\frac{t(t-1)}{2} \pi \ell ^2\right) \\= & {} \frac{p_5\pi }{16}\ell ^2 \left( \sum _{t=1}^{m-1}t-\frac{\pi \ell ^2}{2}\sum _{t=1}^{m-1}t^3+\frac{\pi \ell ^2}{2}\sum _{t=1}^{m-1}t^2\right) \\= & {} \frac{p_5\pi }{16}\ell ^2 \left( \frac{m(m-1)}{2}-\frac{\pi \ell ^2}{2}\frac{(m-1)^2m^2}{4}\right. \\&\quad \left. +\frac{\pi \ell ^2}{2}\frac{(m-1)m(2m-1)}{6}\right) \\\ge & {} \frac{p_5\pi }{16}\ell ^2 \left( \frac{m(m-1)}{2} - \frac{\pi \ell ^2m^4}{8}\right) \\= & {} \frac{p_5\pi }{16}\left( \frac{\alpha ^2}{2}-\frac{\pi \alpha ^4}{8}-\frac{\alpha ^2}{2m}\right) >0, \end{aligned}$$

for m sufficiently large. Thus, if $\ell = \frac{\alpha }{m}$ for $\alpha \le \sqrt{1/\pi }$, then $Pr[p(M)>0]\not \rightarrow 0$ as $m\rightarrow \infty$. However, since increasing $\ell$ cannot decrease $Pr[p(M)>0]$, it follows that if $\ell = \Omega (\frac{1}{m})$, then $Pr[p(M)>0]\not \rightarrow 0$ as $m\rightarrow \infty$. $\square$

4 Concluding remarks

In this paper, we derived tight bounds on the number of intersection points and circuits of different families of segment sets. Such bounds on p and c in terms of m can yield better bounds on the time and space complexities of existing algorithms. In particular, in Sect. 3, we considered segment Halin graphs, segment cactus graphs, segment $K_3$-free graphs, and segment maximal planar graphs. These classes of segments are mostly non-overlapping and thus constitute a significant part of all sets of segments; for instance, segment Halin graphs and segment $K_3$-free graphs are disjoint, as are segment maximal planar graphs and segment cactus graphs (for $m\ne 3$). Some other interesting families to consider are segment bipartite planar graphs and segment maximal outerplanar graphs. By a similar reasoning as in Proposition 3, it can be shown that for a segment maximal outerplanar graph, $p\ge \left\lceil (m+3)/2\right\rceil$ and $c\ge \left\lceil (m-1)/2\right\rceil$. However, we have not been able to find exact or asymptotic tight upper bounds on p and c. A construction of segment maximal outerplanar graphs with $p=2m-6$ and $c=2m-8$ is shown in Fig. 10, but in general, this construction is not the best possible. However, we conjecture that the upper bounds for both p and c are linear in m.

Fig. 10

An instance of a class of segment maximal outerplanar graphs with $p=2m-6$ and $c=2m-8$; we conjecture that for segment maximal outerplanar graphs, p and c are both O(m)

In Sect. 3.5, we investigated randomly generated sets of segments with fixed length. A related direction for future work is to explore properties of Buffon segment sets with non-uniform lengths; for example, the lengths of the segments could be random variables with a given probability distribution. The expected value of other parameters of $G_M$ (such as independence number, maximum matching, etc.) could also be explored, for a Buffon set M with uniform or non-uniform length segments.