CODEWITHSUNDEEP
javamathoptimizationgeometry
Rasmond
Rasmond

Reputation: 512

How to find the furthest point from other given points in Java

I have a given S point (red on the graph) and n other points (black on the graph). I want to find a point P, in a distance of 1 from S, which is the furthest from all the black points (in this case - the sum of distances between P and each point should is the highest).

graph

As P is 1 away from S, we can tell that y = √(1 - x^2).

The analitical way I would personally use would be to:

  1. Calculate the sum of the distances
    • Q - P = √((Qx - Sx - x)^2 + (Qy - Sy - √(1 - x^2))^2) (repeat of all n points and sum up),
  2. Calculate the derivative of the obtained expression,
  3. Calculate roots of the derivative and find maximums (in the domain),
  4. Calculate values at the ends of the intervals in the domain,
  5. Choose the correct X.

What would be the most efficient way to do this in Java and what libraries could be used? I heard about libraries allowing to do this analyticaly, but it sounds complicated and slow so I was searching for any numerical ideas, but couldn't find any.

Upvotes: 2

Views: 1186

Answers (3)

user1884155
user1884155

Reputation: 3736

EDIT: The algorithm below doesn't work as explained in the comments. I'll keep it here as a reference.

This might a bit naive, but how about:

  • Find the average of all black points. This can be as easy as sum(x-coord)/n and sum(y-coord)/n. This "average" point will likely NOT be on the circle. Let's call this point "A"
  • Draw a line from this average point towards S = |AS|
  • Continue this line along the same angle until you reach the circle at the other side of S. Let's call this point O (opposite). You now have line |ASO|.
  • O can be calculated because you know the radius of the circle is 1, and by definition this point is the furthest point on the red circle away from the average point A, and from here it follows no other point on the circle will be further away from all black points.

Corner-case: if all black points are point-symmetrical around the origin (for example, one point at -2,-2 and one point at 2,2; then the solution above would have no answer because A (the average point) would equal S (origin 0,0). You can do an additional check for A being equal to S and then throw an exception.

Upvotes: 0

gimme_danger
gimme_danger

Reputation: 798

First of all, it seems that O(N^2) is not so bad in the worst case for this problem. Because each call to cost function costs O(N). Consider this situation: N black points, which lie on another circle (R > 1, center in S) and split this new circle into N equal arcs. In this symmetric case, we have N maximums. Just to check them it takes O(N^2) — compute cost function in each point. So I think any algorithm which examines all local extremums will have at least O(N^2) in the worst case.

Here my solution sketch for general case:

  • If {Q_j} are black points, let`s define {O_j} so that each O_j is the closest point to Q_j which lies on the red circle around S. Points {O_j} split the circle into n arcs. We can calculate each O_j coords easily.

  • It seems that cost function which we are trying to optimize has only one local extremum within each arc (this part need more accurate proof), so we could find these extremums by ternary search -- linearithmic complexity. We need to check O_j for local extremums as well -- linear complexity.

  • Totally, we have to check O(NlogN) points, each check costs O(N). At least this method is more convenient than checking every point on circle with small epsilon.

Upvotes: 0

Quedlin
Quedlin

Reputation: 11

Follow the path of the circle in SMALL incrementials. Calculate the sum of distances for each point along the circle. Find the position where the sum of distances are the maximum. Done. java.lang.Math is enough for this. No need of extra libraries. Look up trigonometry.

SP segment's angle is phi. You go from 0 to 2*pi (remember it uses radians). Increment phi with a small number in your loop.

Something like:

  • phi=0.0;
  • maxSumDistance = 0.0;
  • phiAtMaxValue = 0.0;
  • do a loop: phi goes from 0.0 to 2*pi adding a small number to phi each time
  • Inside the loop: if (currentSumDistance > maxSumDistance) then maxSumDistance = currentSumDistance; and phiAtMaxValue = current value of phi (the loop variable);

At the end of the loop You will have the phi angle's value where the sum of distances was the biggest. Then you recalculate the coordinates of P from phi, and the distance of SP.

This might be a bruteforce approach, but calculating derivatives for this seems overkill, and too complicated.

Upvotes: 1

Related Questions