CODEWITHSUNDEEP
java
schauk11erd
schauk11erd

Reputation: 634

Finding local minimum of minima

I have a list of double values (distances between point p0 and a point list L) and I'm looking for their minimum. Then I'm changing the list (which now contains distances between point p1 and the point list L) and compute this new minimum. I repeat this until the new minimum is bigger than the minimum at the previous step.

In pseudo Java code:

double minDistanceTotal = Double.MAX_VALUE;
double minDistanceCurrent = ?????;
while (minDistanceCurrent < minDistanceTotal) {
    Point curPoint = ... // take another point p0, p1, p2...
    // compute current minimum distance
    for (Point otherPoint : pointList) {
        double curDistance = distance(curPoint, otherPoint);
        if (curDistance < minDistanceCurrent) {
            minDistanceCurrent = curDistance;
        }
    }
    // compare it to the total minimum distance
    if (minDistanceCurrent < minDistanceTotal) {
        ... // do something
        minDistanceTotal = minDistanceCurrent;
    }
}

My problem now is that I'm not sure about how to initialize minDistanceCurrent. First I tried Double.MAX_VALUE - 1, but then the while-loop isn't executed at all. After checked the Java API to find the actual value of Double.MAX_VALUE which is 0x1.fffffffffffffP+1023. So I tried 0x1.ffffffffffffeP+1023 as the value for minDistanceCurrent, which seems to work.

But I'm not sure if this is really the second highest double value in Java. So, what's the value I should initialize minDistanceCurrent with? Or is there some different approach to get what I want that I missed?

EDIT: After the answer of @resueman, I realized a flaw in the code. The check of current minimum and total minimum can just be done after a new current minimum is computed and not before (as it is in the condition of the while loop).

The problem was fixed using the following code:

double minDistanceTotal = Double.MAX_VALUE;
double minDistanceCurrent = Double.MAX_VALUE;
while (true) {
    Point curPoint = ... // take another point
    // compute current minimum distance
    for (Point otherPoint : pointList) {
        double curDistance = distance(curPoint, otherPoint);
        if (curDistance < minDistanceCurrent) {
            minDistanceCurrent = curDistance;
        }
    }
    // compare it to the total minimum distance
    if (minDistanceCurrent < minDistanceTotal) {
        ... // do something
        minDistanceTotal = minDistanceCurrent;
    } else {
        break;
    }
}

An alternative would be while(!pointList.isEmpty()) to avoid an infinite loop when the list is empty.

Upvotes: 3

Views: 125

Answers (2)

Manuel Franco
Manuel Franco

Reputation: 56

If I'm not wrong, your loop will execute just once. Either the distances calculated by the 'distance' method are lower than MAX_VALUE or overflow the double. In any case, your last 'if' will set current and total distances equal, hence getting you out of the loop. I doubt this is what you really want.

Probably you want just to make minDistanceTotal = minDistanceCurrent just at beginning of the loop, and probably you want to use BigDecimal instead of double to avoid overflowing and inaccurate calculations, but I can't really say as I don't get the idea behind your algorithm.

Summarizing:

  1. Be careful on how you calculate distances inside your "distance(curPoint, otherPoint)", in particular consider overflowing effects. Maybe use BigDecimal instead of Double.
  2. Get ride of the last if and change it for whatever you really need to do.

Hope it helps somehow.

Upvotes: 0

resueman
resueman

Reputation: 10613

It looks like you only want to break out of the loop after this block of code is called

if (minDistanceCurrent < minDistanceTotal) {
    ... // do something
    minDistanceTotal = minDistanceCurrent;
}

If that's the case, then I'd suggest changing your while loop to either while(true) and putting a break in the if statement, or making it while(minDistanceTotal != minDistanceCurrent)

Upvotes: 1

Related Questions