Software Development

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.

is a duplicate

This question has been asked before and has already been answered. It should be marked as a duplicate.

Please enter the URL of the proposed duplicate in the details field below.

not constructive

This question cannot be answered in a way that is helpful to anyone. It's not possible to learn something from possible answers, except for the solution for the specific problem of the asker.

Communities

Comments on Queries to count points lying on arbitrary line

Queries to count points lying on arbitrary line

2 comment threads