An Optimal Algorithm for Computing Many Faces in Line Arrangements

This is one of the most fundamental problems in computational geometry and has been studied extensively. A straightforward algorithm can implicitly determine the non-empty faces of $𝒜(L)$ in $O(m\log n+n^2)$ time, by first constructing $𝒜(L)$, building a point location data structure for $𝒜(L)$ [15, 21, 25], and then finding the non-empty faces using the point location queries for points of $P$. The following upper bounds have been proved on the combinatorial complexity of all non-empty faces of $𝒜(L)$: $O(m^{2/3}{n}^{2/3}+n)$ [10], $O(n\sqrt{m})$ [17], and $O(n+m\sqrt{n})$ [17]. A lower bound of $\mathrm{\Omega }(m^{2/3}{n}^{2/3}+n)$ [17] is also known, which matches the $O(m^{2/3}{n}^{2/3}+n)$ upper bound in [10]. Note that the minimum of the above upper bounds is at most $O(m\log n+n^2)$ regardless of the values of $m$ and $n$. Hence, using the above straightforward approach, $O(m\log n+n^2)$ time is also sufficient to output all non-empty faces explicitly. To have a more efficient algorithm, Edelsbrunner, Guibas, and Sharir [14] first studied the problem and gave a randomized algorithm of $O(m^{2/3-\delta }{n}^{2/3+2\delta }\log n+n\log n\log m)$ expected time, for any $\delta >0$. Subsequently, an improved deterministic algorithm of $O(m^{2/3}{n}^{2/3}{\log }^{5/3}n{\log }^{1.11}(m/\sqrt{n})+(m+n)\log n)$ time was proposed by Agarwal [1]. Also, Agarwal, Matoušek, and Schwarzkopf [2] presented a randomized algorithm of $O(m^{2/3}{n}^{2/3}\log (n/\sqrt{m})+(m+n)\log n)$ expected time. No progress had been made for a while until Wang [26] revisited the problem in SODA 2022 and derived a new deterministic algorithm of $O(m^{2/3}{n}^{2/3}{\log }^{2/3}(n/\sqrt{m})+(m+n)\log n)$ time.

On the other hand, $\mathrm{\Omega }(m^{2/3}{n}^{2/3}+n\log n+m)$ is a lower bound for solving the problem due to the above $\mathrm{\Omega }(m^{2/3}{n}^{2/3}+n)$ lower bound [17] on the combinatorial complexity of all non-empty faces and also because computing a single face in line arrangements requires $\mathrm{\Omega }(n\log n)$ time in the algebraic decision tree model (indeed, a special case of the problem is to compute the lower envelope of all lines, which has an $\mathrm{\Omega }(n\log n)$ time lower bound). In particular, in the symmetric case where $m=n$, $\mathrm{\Omega }(n^{4/3})$ is a lower bound since the worst case combinatorial complexity of all non-empty faces is $\mathrm{\Omega }(n^{4/3})$ [17].

We propose a new (deterministic) algorithm of $O(m^{2/3}{n}^{2/3}+(m+n)\log n)$ time for the problem, which is $O(n^{4/3})$ when $m=n$ and matches the above $\mathrm{\Omega }(n^{4/3})$ lower bound. For the asymmetric case where $m\ne n$, using Ben-Or’s techniques [5], we prove that $\mathrm{\Omega }(m\log n)$ is also a lower bound under the algebraic decision tree model. Combining with the above $\mathrm{\Omega }(m^{2/3}{n}^{2/3}+n\log n+m)$ lower bound, we thus obtain the $\mathrm{\Omega }(m^{2/3}{n}^{2/3}+(m+n)\log n)$ lower bound for solving the problem. As such, our algorithm for the asymmetric case is also optimal. Although our solution only improves the previously best result of Wang [26] by a factor of ${\log }^{2/3}(n/\sqrt{m})$, the result is important for providing the first optimal solution to a fundamental and classical problem in computational geometry.

Our algorithm takes a different approach than the previous work. For example, the most recent work of Wang [26] first solves the problem in $O(n\log n+m\sqrt{n\log n})$ time in the dual setting. Then, the algorithm is plugged into the framework of Agarwal [1] as a subroutine. More specifically, the framework first utilizes a cutting of $L$ to divide the problem into a collection of subproblems and then solves these subproblems using Wang’s new algorithm.

We dispense with the framework of Agarwal [1], and propose a new algorithm for the problem in the primal setting, which is different from that of Wang [26] in the dual setting. One key subproblem is to merge convex hulls, for which our techniques rely on a crucial observation that certain pairs of convex hull boundaries can intersect at most $O(1)$ times. Using a hierarchical cutting of $L$ [8] and combining our new algorithm with Wang’s, we obtain a recursive algorithm that runs in $n^{4/3}\cdot 2^{O({\log }^{\ast }n)}$ time for the symmetric case $m=n$.

To further reduce the $2^{O({\log }^{\ast }n)}$ factor, we resort to the recent techniques from Chan and Zheng [7]: the $\mathrm{\Gamma }$-algorithm framework for bounding algebraic decision tree complexities. More specifically, after $O(1)$ recursive steps in our recursive algorithm, we reduce the problem to $O({(n/b)}^{4/3})$ subproblems of size $O(b)$ each (i.e., in each subproblem, we need to compute the non-empty faces of an arrangement of $b$ lines for $b$ points), with $b=O(\log \log n)$. As $b$ is very small, solving the problem efficiently under the algebraic decision tree model (i.e., only count the number of comparisons) can lead to an efficient algorithm under the conventional computational model (e.g., the real RAM model). With Chan and Zheng’s techniques, we developed an algorithm that solves each subproblem in $O(b^{4/3})$ decision tree complexity (i.e., the algorithm uses $O(b^{4/3})$ comparisons). Since $b$ is small, we are able to build a decision tree for the algorithm in $O(n)$ time. With the decision tree, each subproblem can then be solved in $O(b^{4/3})$ time in the conventional computation model. Consequently, the original problem is solved in $O(n^{4/3})$ time. In addition, using this algorithm as a subroutine, the asymmetric case of the problem where $m\ne n$ can be solved in $O(m^{2/3}{n}^{2/3}+(m+n)\log n)$ time.

Note that our algorithm is not a direct application of Chan and Zheng’s techniques. Nor it is a simple adaption of their algorithm for Hopcroft’s problem. Indeed, in order to fit the $\mathrm{\Gamma }$-algorithm framework, we need to design new procedures for a number of subproblems (notably, our techniques involve shaving log factors to merge convex hulls), which may be interesting in their own right. This is also the case for solving other problems when Chan and Zheng’s techniques are applied. For instance, Chan, Cheng, and Zheng [6] recently used the technique to tackle the higher-order Voronoi diagram problem and presented an optimal algorithm by improving the previous best algorithm by a factor of $2^{O({\log }^{\ast }n)}$. To this end, they had to develop new techniques and made a great effort. On the other hand, there are other problems whose current best solutions have $2^{O({\log }^{\ast }n)}$ factors, but it is not clear whether the $\mathrm{\Gamma }$-algorithm techniques [7, 6] can be used to further reduce these factors. For instance, the biclique partition problem for a set of $n$ points in the plane can be solved in $n^{4/3}\cdot 2^{O({\log }^{\ast }n)}$ time [20, 27]. It has been open whether an $O(n^{4/3})$ time algorithm is possible.

Other related problems have also been studied in the literature, e.g., the segment case where $L$ consists of $n$ line segments. Although faces in an arrangement of lines are convex, they may not even be simply connected in an arrangement of segments. Therefore, the segment case becomes more challenging. It has been proved that the combinatorial complexity of all non-empty faces of the segment arrangement is bounded by $O(m^{2/3}{n}^{2/3}+n\alpha (n)+n\log m)$ [4] and $O(n\sqrt{m}\alpha (n))$ [13], where $\alpha (n)$ is the inverse Ackermann function; a lower bound $\mathrm{\Omega }(m^{2/3}{n}^{2/3}+n\alpha (n))$ [14] was also known. To compute all non-empty faces, Edelsbrunner, Guibas, and Sharir [14] first gave a randomized algorithm of $O(m^{2/3-\delta }{n}^{2/3+2\delta }\log n+n\alpha (n){\log }^{2}n\log m)$ expected time for any $\delta >0$. Agarwal [1] presented an improved deterministic algorithm of $O(m^{2/3}{n}^{2/3}\log n{\log }^{2.11}(n/\sqrt{m})+n{\log }^{3}n+m\log n)$ time. Also, Agarwal, Matoušek, and Schwarzkopf [2] derived a randomized algorithm of $O(n^{2/3}{m}^{2/3}{\log }^{2}n+(n\alpha (n)+n\log m+m)\log n)$ expected time. Wang [26] proposed an $O(n^{2/3}{m}^{2/3}\log n+\tau (n{\alpha }^2(n)+n\log m+m)\log n)$ time deterministic time, where $\tau =\min \{\log m,\log (n/\sqrt{m})\}$. An intriguing question is whether our new techniques for the line case can somehow be utilized to tackle the segment case. One obstacle, for example, is that the problem for the segment case in the dual setting is not “cleanly” defined and thus we do not have a corresponding algorithm in the dual setting.

In part because of the difficulty, a special case has been studied extensively, in which we wish to compute a single face in an arrangement of segments. The problem can be solved in $O(n\alpha (n)\log n)$ expected time using a randomized algorithm [9], or in $O(n{\alpha }^2(n)\log n)$ time using a deterministic algorithm [3]. These algorithms provide improvements over the previous deterministic methods, which required $O(n{\log }^{2}n)$ time [23] and $O(n\alpha (n){\log }^{2}n)$ time [14] respectively. An open problem in this field has been whether it is possible to have an $O(n\alpha (n)\log n)$ time deterministic algorithm. It is worth noting that computing the upper envelope of all segments can be accomplished more efficiently in $O(n\log n)$ time [19].

The online query problems have also been studied, i.e., preprocess a set of lines or segments so that the face containing a query point can be quickly computed; see, e.g., [12, 18, 26].

After introducing notation in Section 2, we present an algorithm in Section 3 that solves the problem in the primal plane. Then, in Section 4, we describe the second algorithm (which is mainly from [26]) that tackles the problem in the dual plane. We combine the two algorithms in Section 5 to obtain our final algorithm. Due to the space limit, many details and proofs are omitted but can be found in the full paper.

A tool that will be frequently used in our algorithm is cuttings [8, 22]. For a region $R$ in the plane, we use $L_R$ to denote the subset of lines of $L$ that intersect the interior of $R$ (we also say that these lines cross $R$ and $L_R$ is the conflict list of $R$).

A cutting for $L$ is a collection $\mathrm{\Xi }$ of closed cells (each of which is a possibly unbounded triangle) with disjoint interiors, which together cover the entire plane [8, 22]. The size of $\mathrm{\Xi }$ is defined to be the number of cells in $\mathrm{\Xi }$. For a parameter $r$ with $1\le r\le n$, a cutting $\mathrm{\Xi }$ for $L$ is a $(1/r)$-cutting if $|L_{\sigma }|\le n/r$ holds for every cell $\sigma \in \mathrm{\Xi }$.

We say that a cutting ${\mathrm{\Xi }}^{\prime }$ $c$-refines another cutting $\mathrm{\Xi }$ if each cell of ${\mathrm{\Xi }}^{\prime }$ is wholly contained within a single cell of $\mathrm{\Xi }$, and if every cell in $\mathrm{\Xi }$ encompasses at most $c$ cells from ${\mathrm{\Xi }}^{\prime }$.

A hierarchical $(1/r)$-cutting, characterized by constants $c$ and $\rho$, consists of a series of cuttings ${\mathrm{\Xi }}_0,{\mathrm{\Xi }}_1,\mathrm{\dots },{\mathrm{\Xi }}_k$ with the following property. ${\mathrm{\Xi }}_0$ has a single cell that is the entire plane. For each $1\le i\le k$, ${\mathrm{\Xi }}_i$ is a $(1/{\rho }^i)$-cutting of size $O({\rho }^{2i})$ that $c$-refines ${\mathrm{\Xi }}_{i-1}$. To make ${\mathrm{\Xi }}_k$ a $(1/r)$-cutting, we select $k=\mathrm{\Theta }(\log r)$ to ensure . Consequently, the size of ${\mathrm{\Xi }}_k$ is $O(r^2)$. As already shown in [8], it can be easily verified that the total number of cells of all cuttings ${\mathrm{\Xi }}_i$, $0\le i\le k$, is also $O(r^2)$, and the total size of the conflict lists $L_{\sigma }$ for all cells $\sigma$ of ${\mathrm{\Xi }}_i$, $0\le i\le k$, is bounded by $O(nr)$. If a cell $\sigma$ within ${\mathrm{\Xi }}_{i-1}$ contains a cell ${\sigma }^{\prime }$ in ${\mathrm{\Xi }}_i$, we call $\sigma$ the parent of ${\sigma }^{\prime }$ and ${\sigma }^{\prime }$ a child of $\sigma$. In the following, we often use $\mathrm{\Xi }$ to denote the set of all cells of all cuttings ${\mathrm{\Xi }}_i$, $0\le i\le k$.

For any $1\le r\le n$, a hierarchical $(1/r)$-cutting of size $O(r^2)$ for $L$ (together with the conflict lists $L_{\sigma }$ for all cells $\sigma$ of ${\mathrm{\Xi }}_i$ for all $i=0,1,\mathrm{\dots },k$) can be computed in $O(nr)$ time [8].