Gebruiker:Niknetniko/Kladblok/Dichtste puntenpaar

Het dichtste puntenpaar is in het rood aangeduid.

Het vinden van het dichtste puntenpaar is een probleem uit de computationele meetkunde, waarbij men, gegeven $n$ punten in een metrische ruimte, de twee punten wenst te vinden die het dichtst bij elkaar liggen. Gesteld in de Euclidische ruimte was dit probleem een van de eerste problemen die bestudeerd is in de computationele complexiteitstheorie. Een naïeve oplossing voor dit probleem heeft een computationele complexiteit van $O(n^{2})$. In de Euclidische ruimte of in een $L^{p}$-ruimte met vaste dimensie $m$ kan het opgelost worden in $O(n\log n)$.

Dit probleem mag niet verward worden met het verwante probleem van het vinden van het dichtste punt voor een gegeven ander punt (nearest neighbour search).

Probleemstelling

Gegeven een verzameling $S$ met $n$ punten uit een $m$-dimensionale metrische ruimte met afstandsfunctie $d$. Zoek het kortste puntenpaar van $S$, met andere woorden twee punten $P$ en $Q$, zodat:

$d(P,Q)=\min \left\{d(p,q):p,q\in S,p\neq s\right\}$

Geschiedenis

Lange tijd dachten onderzoekers dat de computationele ondergrens voor het probleem kwadratisch was. Omdat dit probleem deel uitmaakt van een heleboel andere problemen, impliceerde dit dat de ondergrens voor die problemen ook kwadratisch was. Een eerste oplossing in O(n log n) verscheen in 1974, door Michael Shamos. Hij gebruikte Voronoi-diagrammen om het probleem op te lossen. Een eerste algoritme dat gebruik maakt de verdeel-en-heerstechniek verscheen in 1976. Sindsdien zijn verschillende snellere algoritmen gepubliceerd.

Oplossingen

Brute force

Het dichtste puntenpaar kan gevonden worden door brute force zoeken, wat een complexiteit geeft van $O(n^{2})$, met $n$ het aantal punten. Dit algoritme werkt eenvoudig: overloop alle $n(n-1)/2$ puntenparen, en kies uiteindelijk het paar met de kleinste onderlinge afstand. Hieronder wordt dit algoritme gegeven in pseudocode.

afstand = ∞
# Overloop alle punten van [1, |S|[
for i in range(1, len(S)):
  # Overloop alle punten van [i, |S|]    
  for j in range(i + 1, len(S) + 1):
    p, q = S[i], S[j]
    if d(p, q) < afstand:
      afstand = d(p, q)
      dichtstePaar = (p, q)
return dichtstePaar

Een dimensie

In één dimensie komt het probleem neer op het vinden van het dichtste puntenpaar op een lijn. In dat geval zullen de punten van het dichtste puntenpaar altijd naast elkaar liggen. Het volstaat om:

1. Sorteer de punten op de lijn.
2. Vergelijk voor elk punt de afstand met het volgende punt.

Sorteren kan met een complexiteit van $O(n\log n)$. Het vergelijken van de punten heeft een complexiteit van $O(n)$, waarvoor de totale complexiteit $O(n\log n)$ wordt.

Twee dimensies

Met de verdeel-en-heerstechniek kan het probleem opgelost worden in $O(n\log n)$. We veronderstellen dat de punten gesorteerd zijn volgens hun x-coördinaat.

Aangezien de punten gesorteerd zijn, kan men een imaginaire lijn trekken die de punten in twee ongeveer even grote helften verdeeld: $S_{l}$ en $S_{r}$. Dit is de snijlijn. Het puntenpaar met de kleinste afstand ligt nu ofwel volledig in de linkerhelft, ofwel volledig in de rechterhelft, ofwel ligt één punt in de linkerhelft en één punt in de rechterhelft.

Noem $d_{l}$ de afstand van het dichtste puntenpaar in $S_{l}$, $d_{r}$ de afstand van het dichtste puntenpaar in $S_{r}$ en $d_{m}$ de afstand van het dichtste puntenpaar waarbij elk punt in een andere helft ligt. De afstanden $d_{l}$ en $d_{r}$ kunnen recursief berekend worden.

Er rest nog het berekenen van $d_{m}$. Op het eerste zicht lijkt het dat hier opnieuw een vergelijking van met alle punten nodig is, waardoor de complexiteit $O(n^{2})$ wordt. Een eerste observatie is dat enkel de punten die op een afstand $d=\min(d_{l},d_{r})$ van de snijlijn liggen relevant zijn. De punten die verder van de snijlijn liggen kunnen nooit leiden tot een dichtste puntenpaar met een afstand die kleiner is dan de puntenparen die reeds recursief bepaald zijn. Noem de zone aan weerszijde van de snijlijn binnen een afstand $d$ de zoekstrook.

Sorteer nu alle punten in de zoekstrook volgens hun y-coördinaat, waarna de zoekstrook verdeeld wordt in vierkant met zijde $d/2$. In elk vierkant zit hoogstens één punt: indien er meerdere punten in een vierkant zouden zitten, dan zou de afstand tussen deze twee punten kleiner zijn dan $d$, want onmogelijk is (want dan zou dit puntenpaar gevonden zijn als dichtste puntenpaar van de respectievelijke helft).

Voor elk punt in de zoekstrook wordt nu vergeleken met de 8 volgende punten, gesorteerd volgens y-coördinaat. Immers, elk punt ligt in een eigen vierkant, en punten die meer dan 2 vierkanten verder zijn, liggen sowieso op een afstand $>d$ van het originele punt.

Het resultaat is $\min(d_{l},d_{m},d_{r})$.

De recurrente betrekking voor dit algoritme is $T(n)=T(n/2)+O(n)$: het aantal punten wordt verdeeld in twee, en de complexiteit van het vergelijken in de zoekstrook is lineair: er zijn hoogstens $n$ punten in de zoekstrook, en voor elk punt wordt vergeleken met een constant aantal andere punten. Uit het master-theorem volgt de complexiteit van het algoritme: $O(n\log n)$.

Hogere dimensies

Het verdeel-en-heersalgoritme voor twee dimensies kan veralgemeend worden tot $m$ dimensies. Een inzicht hierbij is dat het zoeken in de zoekstrook neerkomt op het oplossen van het probleem in een lagere dimensie.