我将它们转换为三维坐标，然后使用分而治之的方法，即使用平面而不是直线。这绝对可以正常工作。我们可以放心，因为当仅检查球体上的点时，两个最接近的圆弧距离点（在曲面上行走的距离）也将是最接近的三个3d笛卡尔距离。这将具有运行时间O（nlogn）。

要转换为3-d坐标，最简单的方法是使（0,0,0）成为地球中心，然后您的坐标为（cos（lat） cos（lon），cos（lat） sin（lan）
），sin（lat））。出于这些目的，我使用的是地球半径为1的比例尺，以简化计算。如果要以其他单位表示距离，则以该单位进行测量时，只需将所有数量乘以地球半径即可。

我应该指出，所有这些都假设地球是一个球体。这不完全是一个点，并且点实际上也可能具有高度，因此这些答案并不是真的完全准确，但是几乎在每种情况下它们都非常接近正确。