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

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.

• How are you defining the corners and edges of your rectangles? It sounds like the corners are (lat1,lon1) (lat1,lon2) (lat2,lon2) (lat2,lon1); please confirm. But are the edges which share the same latitude rhumb lines or geodesics?
– cffk
Aug 30, 2018 at 17:25
• @cffk Edited to confirm that your understanding is correct. Also, to Berend, who edited out my color commentary, you are a meanie.
– user1462
Aug 30, 2018 at 19:52
• How about the east-west edges? Are they geodesics or are they lines of constant latitude?
– cffk
Aug 31, 2018 at 11:19
• @cfk Lines of constant longitude, but I think that's implied by the coordinates I gave, no?
– user1462
Aug 31, 2018 at 14:03
• My question was about east-west edges, not north-south ones!
– cffk
Aug 31, 2018 at 14:25

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).

• This is a fantastic answer, thank you. I may diagram it because it seems intuitively weird.
– user1462
Aug 31, 2018 at 20:13