5
$\begingroup$

Consider a set $P$ of $N$ points in the unit square and a set $L$ of $N$ non-vertical lines. Can we count the number of pairs $$\{(p,\ell)\in P\times L: p\; \text{lies above}\; \ell\}$$ in time $\tilde{O}(N)$?

(Here $\tilde{O}(N)$ means $O(N (\log N)^{O(1)})$, or, if you prefer, something looser, such as $O_{\epsilon}(N^{1+\epsilon})$ for $\epsilon>0$ arbitrary.)

Improve this question
$\endgroup$
3
  • $\begingroup$ If it helps, you may assume that the points are well-separated (i.e., they are at distance $\gg 1/N$ or so from each other) and that the slopes of the lines are well-separated as well. In fact, for starters, you may assume that the lines have slopes that are multiples $c, 2 c, \dotsc, N c$ of some $1/N\ll c\ll N$. (No idea whether this actually helps.) $\endgroup$
    – H A Helfgott
    Commented Jan 6, 2023 at 16:02
  • $\begingroup$ (I meant $1/N\ll c\ll 1/N$ in the above comment.) $\endgroup$
    – H A Helfgott
    Commented Jan 6, 2023 at 16:57
  • $\begingroup$ Andrew Peter Mullhaupt points me towards (efficient algorithms for) half-plane range searching (i.e., the technical term for what I am asking) - that looks interesting indeed... $\endgroup$
    – H A Helfgott
    Commented Jan 6, 2023 at 23:12

1 Answer 1

Reset to default
12
$\begingroup$

This problem seeks to count incidences between n points and n halfplanes; it can be addressed as a halfplane range counting problem; see the recent paper by Chan and Zheng (https://arxiv.org/pdf/2111.03744.pdf) for a solution yielding time bound $O(n^{4/3})$. (and see related work on Hopcroft's problem in which one counts incidences between a set of n points and a set of n lines)

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think that the question is about a possibly easier problem, when all halfplanes face downwards. $\endgroup$
    – domotorp
    Commented Jan 7, 2023 at 5:38
  • 2
    $\begingroup$ I don't see right away how that problem can be easier. The general problem (where the half-planes can be upper or lower half-planes) reduces to the problem for lower half-planes: just divide an instance of the general problem into two - one for the "upwards halfplanes" (just turn the page around so they become downwards halfplanes), one for the "downwards halfplanes" - and then add. $\endgroup$
    – H A Helfgott
    Commented Jan 7, 2023 at 9:07
  • $\begingroup$ This is very nice. But can one do better if one knows that the points have $x$-coordinates $1/N, 2/N,\dotsc, 1$, say? And/or that the slopes of the lines are $1/N,2/N,\dotsc,N/N$? $\endgroup$
    – H A Helfgott
    Commented Jan 8, 2023 at 19:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .