Misplaced Pages

In computational geometry, Hopcroft's problem is the problem of testing, for a given system of points and lines in the Euclidean plane, whether at least one of the points lies on at least one of the lines. More generally, one may ask for the number of point–line incidences. Both versions of the problem can be solved in time ${\displaystyle O(n^{4/3})}$, where ${\displaystyle n}$ is the total number of points and lines. This time bound matches the bound of ${\displaystyle O(n^{4/3})}$ on the total number of point-line incidences given by the Szemerédi–Trotter theorem. Hopcroft's problem is named after John Hopcroft, who posed it in the early 1980s. Its computational complexity is closely connected to the complexity of several other problems in computational geometry, including that of three-dimensional Euclidean minimum spanning trees.

Algorithms

One way of solving the problem involves a geometric divide-and-conquer algorithm. For a given system of points and lines, it is possible to use the theory of epsilon-nets to subdivide the plane, for a given parameter ${\displaystyle r}$ into ${\displaystyle O(r)}$ triangular subproblems each crossed by a ${\displaystyle 1/r^{2}}$ fraction of the lines and each containing a ${\displaystyle 1/r}$ fraction of the points. Alternatively, applying the same technique to the projective dual system of dual lines and dual points, one can obtain subproblems each involving a ${\displaystyle 1/r}$ fraction of the input lines and a ${\displaystyle 1/r^{2}}$ fraction of the points. Doing this once each way, for ${\displaystyle r=n^{1/3}}$, would reduce the problem to subproblems of constant size, which can be solved directly. This idea (with a more careful choice of the parameter ${\displaystyle r}$) leads to a time bound of ${\displaystyle O(n^{4/3}\log ^{1/3}n)}$. Here, the extra logarithmic factor comes from the overhead of assigning points and lines to the subproblems that are generated in this way.

The same two-step subdivision process, with a choice of ${\displaystyle r}$ that is smaller by a logarithmic factor, can reduce the given problem to subproblems whose size is a polylogarithmic function of ${\displaystyle n}$, in time ${\displaystyle O(n^{4/3})}$. Repeating this process recursively until the input is reduced to subproblems of constant size, would lead to a time bound of the form ${\displaystyle n^{4/3}2^{O(\log ^{*}n)}}$. Here ${\displaystyle \log ^{*}n}$ denotes the iterated logarithm.

In a 2024 paper, Chan and Zheng showed that there exist algebraic decision trees for Hopcroft's problem whose depth is ${\displaystyle O(n^{4/3})}$. These cannot be used directly to solve Hopcroft's problem, because they have exponential size and cannot be constructed efficiently; however they can be used in combination with the divide-and-conquer methods. Following a suggestion credited to David Eppstein by Jiří Matoušek, Chan and Zheng describe an algorithm that performs a constant number of levels of the recursive algorithm, reducing the problem to many subproblems whose size is an iterated logarithm of the original input size. This is small enough for an optimal decision tree to be constructed by a brute-force search, and then used to solve each subproblem. The result is an algorithm for Hopcroft's problem with total time ${\displaystyle O(n^{4/3})}$.

In a 2024 preprint, Andrejevs, Belovs, and Vihrovs have announced a quantum algorithm for Hopcroft's problem that runs in time ${\displaystyle {\tilde {O}}(n^{5/6})}$, where the ${\displaystyle {\tilde {O}}}$ notation hides logarithmic factors. This is substantially below the best known time bound for a classical algorithm.

Lower bounds

A natural limitation on Hopcroft's algorithm is the number of point–line incidences, which could be ${\displaystyle \Theta (n^{4/3})}$ by the Szemerédi–Trotter theorem. This would also provide a lower bound on algorithms for listing all point–line incidences, but not for detecting whether there is an incidence or counting the incidences.

The divide-and-conquer algorithms for Hopcroft's algorithm operate purely by subdividing the plane in which the input points and lines are given and its dual projective plane. Jeff Erickson proved a lower bound, according to which algorithms that operate in this way must take time ${\displaystyle \Omega (n^{4/3})}$. However, methods based on algebraic decision trees do not fit this model, and Erickson's lower bound does not apply to algebraic decision trees. If there exist algebraic decision trees for the problem with depth ${\displaystyle o(n^{4/3})}$, they could be used in the same way to solve Hopcroft's problem in time ${\displaystyle o(n^{4/3})}$.

References

1. ^ Chan, Timothy M.; Zheng, Da Wei (2024), "Hopcroft's problem, log shaving, two-dimensional fractional cascading, and decision trees", ACM Transactions on Algorithms, 20 (3): 24, doi:10.1145/3591357
2. ^ Szemerédi, Endre; Trotter, William T. (1983), "Extremal problems in discrete geometry", Combinatorica, 3 (3–4): 381–392, doi:10.1007/BF02579194, MR 0729791
3. ^ Erickson, J. (1996), "New lower bounds for Hopcroft's problem", Discrete & Computational Geometry, 16 (4): 389–418, doi:10.1007/BF02712875, MR 1414963
4. Chazelle, Bernard (1993), "Cutting hyperplanes for divide-and-conquer", Discrete & Computational Geometry, 9 (2): 145–158, doi:10.1007/BF02189314, MR 1194032
5. ^ Matoušek, Jiří (1993), "Range searching with efficient hierarchical cuttings", Discrete & Computational Geometry, 10 (2): 157–182, doi:10.1007/BF02573972, MR 1220545
6. Andrejevs, Vladimirs; Belovs, Aleksandrs; Vihrovs, Jevgēnijs (2024), Quantum algorithms for Hopcroft's problem, arXiv:2405.01160

• Computational geometry