7
$\begingroup$

Suppose we have $N$ points on $XY$ plane, ie. $(x, y)$ and $x, y \in Z$ and multiple queries where each query is of the form $y = mx + c$ and $m, c \in Z$.

Is it possible to count number of points that lie on the given line more efficiently than $O(N)$ per query?

I believe some preprocessing might help or some data structure like QuadTree that counts points inside arbitrary rectangle.

The queries are offline so if it's possible using some batch processing technique or even SQRT optimization it would be better than naive brute force.

Improve this question
$\endgroup$
6
  • $\begingroup$ What do you call SQRT optimization ? $\endgroup$
    – user16034
    May 28 at 19:23
  • 1
    $\begingroup$ IMO, as the queries are offline, you should ask for an algorithm to perform $M$ queries in time better than $O(MN)$. $\endgroup$
    – user16034
    May 28 at 19:26
  • $\begingroup$ @YvesDaoust I meant some optimizations which combine 2 algorithms one which runs in O(x) and other in O(N/x) when input size is less than root(N) or larger, or even Offline query algorithms like Mo's algorithm which uses SQRT ideas to get runtimes of the form O(N root(N)), better than brute force even if not most optimal. $\endgroup$
    – bihariforces
    May 29 at 15:14
  • $\begingroup$ What do you call SQRT ideas ? $\endgroup$
    – user16034
    May 29 at 15:19
  • $\begingroup$ @YvesDaoust cses.fi/book/book.pdf Chapter 27 of this book is about such techniques, I am not good at these but know that some problems can be optimized by such ideas. $\endgroup$
    – bihariforces
    May 29 at 15:57

2 Answers 2

Reset to default
8
$\begingroup$

Note that via point-line duality (i.e. mapping each point $(p_x,p_y)$ to the line $y=p_x x - p_y$ and each line $y=mx +c$ to the point $(m,-c)$), this problem is equivalent to: given a set $L$ of $n$ lines, count the number of lines that contain a query point.

The subdivision of the plane induced by $L$ is known as an arrangement of lines $\mathcal{A}(L)$, and has a complexity of $O(n^2)$. A doubly connected edge-list (DCEL) that represents the faces, edges and vertices of $\mathcal{A}(L)$ can be computed in $O(n^2)$ time. For each vertex of the DCEL, store the number of lines intersecting it. Next, construct a trapezoidal decomposition of the DCEL in $O(n^2\log n)$ expected time.

When given a query point, first find the trapezoid that contains the point, then traverse the boundary edges and vertices of the trapezoid to determine whether the query point coincides with an edge, face, or vertex. Finding the trapezoid takes $O(\log n)$ expected time, the rest takes $O(1)$, as a trapezoid has $O(1)$ vertices and edges.

So, with $O(n^2\log n)$ expected preprocessing time and $O(n^2)$ expected storage, queries can be answered in $O(\log n)$ expected time. This is one way to get a smaller query time, although the storage requirement is rather large, so there may be a better way.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Your notation is misleading. If there are $M$ queries, the preprocessing takes $O(M^2\log M)$ time and a query $O(\log M)$. [Though it is likely that $\log M\ll N$.] $\endgroup$
    – user16034
    May 29 at 15:21
  • $\begingroup$ @YvesDaoust The preprocessing here does not depend on the number of queries, only on the size of the arrangement of lines, which consists of $n$ lines (each line being the dual of an input point). If there are $M$ queries, the total time of the algorithm (including preprocessing) is $O(n^2\log n + M\log n)$ time. I think it is quite standard to report the time per query for data structures. $\endgroup$
    – Discrete lizard ♦
    May 29 at 16:46
  • $\begingroup$ Sorry, my bad, I mislead myself. As I wrote in a comment, the queries being offline, any total query time better than $O(NM)$ could do. But then the notion of preprocessing becomes fuzzy. $\endgroup$
    – user16034
    May 29 at 16:53
0
$\begingroup$

Depending on the size of N (the number of points) and M (the number of queries), it may be enough to precompute all the answers: there are no more than N*N possible lines. :-) You can represent all lines by exact slope and 0-crossing using reduced (i.e. simplified) rationals. Then search. Binary search, hashing, perfect hashing, etc.

With the constraint that slope and 0-crossing are integers in queries you can probably discard some lines, and perhaps use some optimizations such as using an array indexed by m,c. You can run a prepass to compute minimum and maximum m and c.

Update: this idea fails for the case where the answer is exactly one. See comments. :-(

Improve this answer
$\endgroup$
7
  • $\begingroup$ With the preprocessing described in this answer, it seems $O(N)$-time is still needed to find whether a queried line passes at least one given point or not. $\endgroup$
    – John L.
    May 29 at 20:51
  • $\begingroup$ @JohnL. Good point. OP asks for counting points on query line, that's cheap enough. To find point-on-line you'd probably use some other structure and algorithm, but with this answer, instead of point count store with each line all points on the line in some favourable access structure (e.g. a sorted array gives $O(N \log N)$ lookup). $\endgroup$
    – Pablo H
    May 30 at 13:21
  • $\begingroup$ @JohnL. OTOH, to know if a given line L passes through a given point P, just plug P's coordinates into L's [implicit] equation. P satisfies L's equation iff it's on the line. (In exact arithmetic, such as integers or rationals. Floating point is another problem. ;-) ) $\endgroup$
    – Pablo H
    May 30 at 13:25
  • $\begingroup$ Please tell me how you will determine whether no point pass through the queried line. No, I do not care to find point-on-line. You will need some data structure that is similar to the trapezoidal decomposition of the DCEL given in Discrete lizard's answer to do it in $O(\log n)$ time. $\endgroup$
    – John L.
    May 30 at 13:35
  • $\begingroup$ @JohnL. The idea in this answer is: iterate al pairs of points, compute line, store in access structure AS (e.g. hash, array, dictionary, depending on context). Then search AS for query line; if not found, then no point passes through the query line. That, or I'm missing something. :-) $\endgroup$
    – Pablo H
    May 30 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.