Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Post History
Suppose we have N points on XY plane, ie. (x, y) and x, y are integers and multiple queries where each query is of the form y = mx + c and m, c are integers. Is it possible to count number of poin...
#2: Post edited
by
theabbie
·
2023-05-28T16:47:54Z (over 1 year ago)
Removed unsupported Mathjax
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.
- Suppose we have N points on XY plane, ie. (x, y) and x, y are integers and multiple queries where each query is of the form y = mx + c and m, c are integers.
- 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.
#1: Initial revision
by
theabbie
·
2023-05-28T16:46:44Z (over 1 year ago)
Queries to count points lying on arbitrary line
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.