Solve k-Nearest Places by Latitude/Longitude

Given a set of geographic coordinates and a query point, return the k nearest locations. Describe how you compute great-circle distance (e.g., Haversine), choose data structures or indexes (e.g., k-d tree variants, geohash bucketing, or R-tree), and bound runtime and memory complexity. Discuss handling of Earth curvature, antimeridian crossings, and performance at scale, including approximate search and batching.

k-Nearest Places by Latitude/Longitude (Haversine)

You are given a list of geographic locations, each as a [latitude, longitude] pair in decimal degrees, a query point [latitude, longitude], and an integer k.

Return the k locations closest to the query point, ordered from nearest to farthest, where distance is the great-circle distance computed with the Haversine formula on a sphere of radius 6371 km.

Rules:

• Return the place coordinate pairs themselves (not indices), in increasing order of distance.
• If two places are equidistant, the one that appears earlier in the input list comes first (stable tie-break by original index).
• If k is greater than the number of places, return all places sorted by distance.
• If the input list is empty, return an empty list.

Haversine distance between points (lat1, lon1) and (lat2, lon2), with all angles converted to radians:

  a = sin^2(Δlat/2) + cos(lat1)·cos(lat2)·sin^2(Δlon/2)
  c = 2·atan2(√a, √(1−a))
  distance = R · c,  R = 6371 km

Because Haversine works on angular differences along the sphere, it naturally handles the antimeridian (longitudes near ±180) without special casing — the cosine/sine terms wrap correctly.

Constraints

• 0 <= len(places) <= 10^5
• Each coordinate is [latitude, longitude] with -90 <= latitude <= 90 and -180 <= longitude <= 180 (decimal degrees).
• 1 <= k (k may exceed len(places); in that case return all places).
• Distances use a spherical Earth model with R = 6371 km (Haversine).
• Ties in distance are broken by the original index (earlier place first).

Examples

Example 1

Input: ([[40.7128, -74.0060], [34.0522, -118.2437], [41.8781, -87.6298], [29.7604, -95.3698]], [40.0, -75.0], 2)
Output: [[40.7128, -74.006], [41.8781, -87.6298]]

Explanation: Query is near New York. NYC (40.71, -74.01) is closest, then Chicago (41.88, -87.63) — both nearer than Los Angeles and Houston.

Example 2

Input: ([[0.0, 0.0], [10.0, 10.0], [1.0, 1.0]], [0.0, 0.0], 1)
Output: [[0.0, 0.0]]

Explanation: The query coincides exactly with the first place (distance 0), so it is the single nearest.

Hints

1. Haversine needs radians: convert every latitude/longitude with math.radians before applying sin/cos. The constant R = 6371 km only scales the result, so it does not affect the ordering — but use it for consistency.
2. You only need the relative ordering of distances. You could even sort by the chord term a instead of the full distance, since the Haversine distance is monotonic in a — but computing the real distance is clearer and fast enough.
3. For deterministic output when two places are equidistant, sort by (distance, original_index). When k << n, a max-heap of size k gives O(n log k) instead of O(n log n).