Closest Pair of Cities

/ Exams & Certification / By

Problem (2): Closest Pair of Cities (20 points): The great-circle distance between two locations on earth is the shortest distance over the earth’s surface (giving an ‘as-the-crow-flies’ distance between the points, ignoring any irregularities). Given the latitude
(radians) and longitude
(radians), the distance between two locations 1 and 2 can be calculated using the “Haversine” folrmula:

where R = 6371. 137 km is the mean Earth’s radius,
,
and atan2() is the 4 quadrant arctangent. Latitude and longitude are usually given in DMS units (Degree, Minutes, Seconds). Latitude is North (N) (0 to +90°), or South (S) (0 to 90°), 0 is the equator. Longitude is East (E) (0 to +180°) or West (W) (0 to 180°), 0 is the prime meridian (Greenwich, England). To convert to radians, we first convert to decimal: a (Decimal Degrees) = degrees + (minutes/60) + (seconds/3600) with a (-) sign for (S) latitudes and (W) longitudes. Then we convert to radians using a(radians) = a (Decimal Degrees) × ? / 180° The Haversine formulas are for calculations on the basis of a spherical earth, ignoring ellipsoidal effects, which is accurate enough for most purposes In fact, the earth is very slightly ellipsoidal; using a spherical model gives errors typically up to only 0.3%. The Problem: Given the locations (Latitude, Longitude) of major population cities on Earth, design and implement a Brute Force algorithm to find the top N different closest pair of cities sorted in increasing order of their separation distance. Report results for the top 10 different closest pair of cities. The data for major population cities on Earth are provided in the Excel file: City List 1

The Correct Answer and Explanation is:

To solve this problem, we need to implement the Haversine formula to compute the great-circle distance between pairs of cities, then use a brute-force approach to find the closest pairs. Here’s how we can break down the problem:

1. Data Conversion (Degrees to Radians)

The first step involves converting the latitude and longitude values from DMS (Degree, Minute, Second) format to decimal degrees and then converting those decimal degrees to radians.

  • Step 1.1: Convert DMS to Decimal Degrees: Decimal Degrees=degrees+minutes60+seconds3600\text{Decimal Degrees} = \text{degrees} + \frac{\text{minutes}}{60} + \frac{\text{seconds}}{3600}Decimal Degrees=degrees+60minutes​+3600seconds​ If the latitude is in the southern hemisphere (South), or the longitude is in the western hemisphere (West), you will apply a negative sign.
  • Step 1.2: Convert Decimal Degrees to Radians: Radians=Decimal Degrees×(π180)\text{Radians} = \text{Decimal Degrees} \times \left(\frac{\pi}{180}\right)Radians=Decimal Degrees×(180π​)

2. Haversine Formula

Given two cities with coordinates (lat1,lon1)(\text{lat}_1, \text{lon}_1)(lat1​,lon1​) and (lat2,lon2)(\text{lat}_2, \text{lon}_2)(lat2​,lon2​), the great-circle distance ddd between them is calculated using the Haversine formula:a=sin⁡2(Δlat2)+cos⁡(lat1)⋅cos⁡(lat2)⋅sin⁡2(Δlon2)a = \sin^2\left(\frac{\Delta\text{lat}}{2}\right) + \cos(\text{lat}_1) \cdot \cos(\text{lat}_2) \cdot \sin^2\left(\frac{\Delta\text{lon}}{2}\right)a=sin2(2Δlat​)+cos(lat1​)⋅cos(lat2​)⋅sin2(2Δlon​)c=2⋅atan2(a,1−a)c = 2 \cdot \text{atan2}\left(\sqrt{a}, \sqrt{1-a}\right)c=2⋅atan2(a​,1−a​)d=R⋅cd = R \cdot cd=R⋅c

Where:

  • Δlat=lat2−lat1\Delta\text{lat} = \text{lat}_2 – \text{lat}_1Δlat=lat2​−lat1​
  • Δlon=lon2−lon1\Delta\text{lon} = \text{lon}_2 – \text{lon}_1Δlon=lon2​−lon1​
  • RRR is the radius of the Earth, which is given as 6371.137 km.

3. Brute Force Algorithm

To find the top N closest pairs of cities, we can use a brute-force approach:

  1. Step 3.1: Loop through all pairs of cities and calculate the distance between each pair using the Haversine formula.
  2. Step 3.2: Store the distances and the corresponding city pairs in a list of tuples, where each tuple is (distance,city1,city2)(\text{distance}, \text{city}_1, \text{city}_2)(distance,city1​,city2​).
  3. Step 3.3: Sort the list of distances in ascending order.
  4. Step 3.4: Return the top N closest pairs (for example, the top 10).

4. Implementation Outline

Here’s a Python implementation outline:

pythonCopyEditimport math

# Haversine Formula to calculate distance
def haversine(lat1, lon1, lat2, lon2):
    R = 6371.137  # Radius of the Earth in km
    lat1, lon1, lat2, lon2 = map(math.radians, [lat1, lon1, lat2, lon2])  # Convert to radians

    dlat = lat2 - lat1
    dlon = lon2 - lon1

    a = math.sin(dlat / 2)**2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlon / 2)**2
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))

    return R * c  # Distance in km

# Brute-force algorithm to find closest pairs
def find_closest_pairs(cities, N=10):
    distances = []
    num_cities = len(cities)
    
    # Iterate over all pairs of cities
    for i in range(num_cities):
        for j in range(i + 1, num_cities):
            city1, lat1, lon1 = cities[i]
            city2, lat2, lon2 = cities[j]
            dist = haversine(lat1, lon1, lat2, lon2)
            distances.append((dist, city1, city2))
    
    # Sort the distances in ascending order
    distances.sort(key=lambda x: x[0])

    # Return the top N closest pairs
    return distances[:N]

# Example usage
cities = [
    ("City1", 40.7128, -74.0060),  # New York (Lat, Lon)
    ("City2", 34.0522, -118.2437), # Los Angeles
    ("City3", 51.5074, -0.1278),   # London
    # Add more cities here...
]

top_10_closest_pairs = find_closest_pairs(cities)
for dist, city1, city2 in top_10_closest_pairs:
    print(f"Distance between {city1} and {city2}: {dist:.2f} km")

5. Explanation of the Code:

  • Haversine function: This function takes the latitudes and longitudes of two cities, converts them to radians, and computes the great-circle distance using the Haversine formula.
  • Brute-force closest pair algorithm: This algorithm iterates through all unique pairs of cities, calculates the distance between them, and stores the result. It then sorts the results and returns the top N closest pairs.

6. Time Complexity:

  • The time complexity of the brute-force approach is O(n2)O(n^2)O(n2), where nnn is the number of cities. This is because we are checking all possible pairs of cities. The sorting step adds an additional O(n2log⁡n)O(n^2 \log n)O(n2logn) due to the sorting of the distances.

Conclusion:

This brute-force approach allows us to calculate the closest pairs of cities based on the great-circle distance, leveraging the Haversine formula. By iterating over all pairs and sorting the results, we can easily find the top N closest pairs and sort them by distance.

Related Posts

Scroll to Top