3

Consider some points on a 2d plane and function f(x)=ax, where b=0. Let's say a point is a 1x1 square.

Now we want to tell how many points is between f(x) function and y line, as in picture below.

Black points are valid, white not. We also say point is valid if it:

  • intersects with the y axis;
  • or with the function f(x);
  • or is between them.

As denoted in the picture :

enter image description here

How can we solve this, assuming that we don't remove any of the points and we don't add them? Is there any other approach than standard brute force?

2
  • is it like this one ceee.rice.edu/Books/LA/leastsq/index.html
    – user466534
    Oct 19, 2011 at 20:36
  • Hey, generally i have some points on a plane and i want to find this function with simple binary search ( i mean find that a in f(x)=ax )to have maximum points which are valid and their amount doesn't exceed some value X. Least Squares approximations seems like good method for finding this this function, but i don't really know how to make it work. Could you elaborate if this method fits to my problem? Thanks
    – Martin Blu
    Oct 20, 2011 at 13:03

2 Answers 2

1

If I am understanding this right the points are random and given to you by their coordinates, and the line is also given to you. If that is the case, there cannot be any a priori knowledge about any relationship between the points, so you'd have to go through them, in the order given, and compare their x coordinate with 0 and their y coordinate with f(x). If a point passes the check you increment the counter, otherwise you don't. The algorithm runs in O(n) time and I highly doubt you can do any better than that without some extra information about the points.

0

The question is quite unclear but it appears from comment "I mean find that a in f(x)=ax to have maximum points which are valid and their amount doesn't exceed some value X" that you want to find a such that N(a)=X, where by N(a) I mean number of points right of the y axis and above line y=ax; or if no such a exists, find a such that m = N(a)<X and N(b)<m implies N(b)<X.

Here's an O(n*ln(n)) algorithm: For each point p, excluding any p below y=0, compute slope M_p as ratio of p's y and x coordinates, or DBL_MAX if x=0. Sort the M's into ascending order (this is the O(n*ln(n)) step), and call the sorted array S.

Now we will set up an array T such that when any X is given, S[T[X-1]] is a slope that will place X points on or above that slope:

   S[n] = DBL_MAX;
   for (k=0, j=n-1; k<=n; --j) {
      T[j] = k;
      do ++k; while (S[k]==S[k-1] && k<=n);
   }

Thereafter, let any X be given. Let h = T[X-1]. If h<n then N(S[h]) <= X; if h==n, there are multiple points on the Y axis and no finite slope will work.

This algorithm uses time O(n*ln(n)) and space O(n) to preprocess a set of n first-quadrant points, and thereafter uses time O(1) to find an a for any given X, 0 < X <= n, such that N(a) = X, if such a exists, else returns a such that N(a) < X < N(b) if b>a, else returns DBL_MAX.

Your Answer

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

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