Constructing Many Faces in Arrangements of Lines and Segments

Abstract

We present new algorithms for computing many faces in arrangements of lines and segments. Given a set $S$ of $n$ lines (resp., segments) and a set $P$ of $m$ points in the plane, the problem is to compute the faces of the arrangements of $S$ that contain at least one point of $P$. For the line case, we give a deterministic algorithm of $O(m^{2/3}{n}^{2/3}{\log }^{2/3}(n/\sqrt{m})+(m+n)\log n)$ time. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of ${\log }^{2.22}n$ and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of ${\log }^{1/3}n$ in certain cases (e.g., when $m=\Theta (n)$). For the segment case, we present a deterministic algorithm of $O(n^{2/3}{m}^{2/3}\log n+\tau (n{\alpha }^2(n)+n\log m+m)\log n)$ time, where $\tau =\min \{\log m,\log (n/\sqrt{m})\}$ and $\alpha (n)$ is the inverse Ackermann function. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of ${\log }^{2.11}n$ and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of $\log n$ in certain cases (e.g., when $m=\Theta (n)$). We also give a randomized algorithm of $O(m^{2/3}{K}^{1/3}\log n+\tau (n\alpha (n)+n\log m+m)\log n\log K)$ expected time, where $K$ is the number of intersections of all segments of $S$. In addition, we consider the query version of the problem, that is, preprocess $S$ to compute the face of the arrangement of $S$ that contains any query point. We present new results that improve the previous work for both the line and the segment cases.

arXiv commentTo be presented at SODA 2022