If rectangle corner points have same nearest neighbor, does whole interior?

Question

If all four corners of a spherical (but actually WGS84/elliptical) rectangle are closest to a given point p in a set S, does that necessarily mean all points inside the rectangle are also closest to p?

By spherical rectangle, I mean a polygon with coordinates:

{lon1, lat1}, {lon1, lat2}, {lon2, lat2}, {lon2, lat1}, {lon1,lat1}

(with the last point just to close off the polygon if necessary) for two longitudes lon1 and lon2 and two latitudes lat1 and lat2.

These are lines of constant latitude and longitude, not geodesics.

I'm trying to coax Mathematica into creating a geographical Voronoi map (https://github.com/barrycarter/bcapps/blob/master/REDDIT/bc-metro.m). This isn't too hard to do if I assume the Earth is spherical, but, I've decided to do this using the Earth's true shape, or at least WGS84.

Mathematica does have a WGS84 accurate GeoDistance function, but it's expensive to evaluate, so I want to use it as few times as possible.

My plan is to break up my region into latitude/longitude rectangles, and, if the 4 corner points are all closest to the same point in my set, assume the entire rectangular region is also closest to that point.

I'm pretty sure I could prove this on a perfect sphere, but I'm worried that it might not be true on an ellipsoid.

I created http://test.barrycarter.info/gmap8.php using this technique (https://github.com/barrycarter/bcapps/blob/master/MAPS/bc-closest-gmap.pl but the code is currently commented out since I tried to use qhull instead), but I have no idea if it's 100% accurate.

Answer 1

I'll assume that the edges of your rectangle are geodesics and not rhumb lines. (In the latter case, it's easy to see that your statement is wrong for spheres and ellipsoids; see below.)

For geodesics, it's a simple matter to find a counterexample for your contention. Consider the rectangle (lat,lon) with a northern edge

c1 = 44 -20
c2 = 44  20

Assume the set S contains two points

p1 = 31.5     0
p2 = 60.04032 0

You can verify that (for the WGS84 ellipsoid) c1 and c2 are closer to p1 than to p2 (by about 9.6 m).

However, the midpoint of the northern edge (c1-c2) of the rectangle

e1 = 45.787757425707873 0

is closer to p2 than to p1 (by about 14.5 m).

For reason for this result is that, in general, median lines are not geodesics. A median line is defined as the locus of points equidistant to two reference points. (They are equivalent for a sphere so there your intuition is correct.)

For more information on median lines, see section 14 of my paper Geodesics on an ellipsoid of revolution.

If you want to answer the question "which point in the set S closest to a given test point" efficiently, then I recommend putting S into a vantage-point tree. My library GeographicLib contains a class NearestNeighbor to do this. See also my discussion on Finding nearest neighbors.

LATER

The question has been revised to make clear that the edges are rhumb lines and not geodesics. In this case the contention fails (badly!) also for a sphere. Consider the rectangle with south edge

d1 = 44 -20
d2 = 44  20

Assume the set S contains two points

q1 = 45.7 0
q2 = 43.9 0

You can verify that (for a sphere of radius 6400 km) d1 and d2 are closer to q1 than to q2 (by about 13.5 km).

However, the rhumb midpoint of the southern edge (d1-d2) of the rectangle

f1 = 44  0

is closer to q2 than to q1 (by about 178.2 km).