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$ Commented Jan 6, 2023 at 16:02
  • $\begingroup$ (I meant $1/N\ll c\ll 1/N$ in the above comment.) $\endgroup$ 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$ 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$ 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$ 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$ Commented Jan 8, 2023 at 19:13

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.