Gegeven is een verzameling punten in het vlak. Gevraagd is het puntenpaar te bepalen dat het dichtst bij elkaar ligt. Implementeer hiervoor een \(\Theta(n \log n)\) verdeel-en-heers algoritme.

Opgave

Schrijf een Python-functie afstandDichtstePuntenpaar die een bestandsnaam als parameter krijgt en die het kwadraat van de afstand tussen het dichtste puntenpaar teruggeeft. De afstand tussen twee punten is de Euclidische afstand. Elke regel van het bestand bevat twee getallen die de x- en y-coordinaat van een punt voorstellen.

Voorbeeld

In het onderstaande voorbeeld veronderstellen we dat het bestand testdata_100_1.txt¹ zich in de huidige directory bevindt.

>>> afstandDichtstePuntenpaar("testdata_100_1.txt")
65

Referentie

• Thomas Cormen, Charles Leiserson, Ronald Rivest en Clifford Stein, “Introduction to Algorithms” (3rd edition), MIT Press, 2009 (par.33.4)