L05 · D&C III — Closest Pair of Points

Τι θα δούμε

Στο L03 γνωρίσαμε το σχήμα «διαίρει και κυρίευε»· στο L04 το είδαμε να λύνει τρία προβλήματα. Εκεί, και στα τρία, το σπάσιμο ήταν εύκολο — κόβεις τον πίνακα στη μέση και τελείωσες.

Εδώ θα δουλέψουμε ένα μόνο πρόβλημα, γεωμετρικό, και θα δούμε ότι αυτή τη φορά ακόμα και το σπάσιμο χρειάζεται σκέψη. Θα συναντήσουμε δύο ιδέες που αξίζει να κρατήσεις:

1. Όταν το αφελές σπάσιμο δεν εγγυάται ισόρροπα κομμάτια, χρειάζεται adaptive διαχωρισμός — διαχωρισμός που εξαρτάται από τα δεδομένα.
2. Το τέχνασμα της ζώνης (strip): μετά την αναδρομή, ένας γεωμετρικός περιορισμός κάνει το βήμα συνδυασμού να τρέχει σε γραμμικό χρόνο, παρότι μοιάζει τετραγωνικό.

Το πρόβλημα

Γιατί μας νοιάζει

Είναι ένα θεμελιώδες γεωμετρικό πρόβλημα — εμφανίζεται κρυμμένο σε πολλά πραγματικά συστήματα:

• Γραφικά υπολογιστών — εντοπισμός συγκρούσεων (collisions) ανάμεσα σε αντικείμενα μιας σκηνής.
• Όραση υπολογιστών — ομαδοποίηση (clustering) κοντινών pixel.
• Γεωγραφικά συστήματα (GIS) — εύρεση του πλησιέστερου ορόσημου σε μια θέση.
• Υπολογιστική χημεία — αλληλεπιδράσεις ανάμεσα στα κοντινότερα άτομα ενός μορίου.
• Έλεγχος εναέριας κυκλοφορίας — ποια δύο αεροσκάφη κινδυνεύουν περισσότερο να συγκρουστούν.

Πόσο γρήγορα γίνεται;

Ωμή βία: $\Theta (n^2)$

Ο ορισμός δίνει αμέσως έναν αλγόριθμο: σύγκρινε όλα τα ζευγάρια σημείων, κράτα το ελάχιστο. Είναι $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\Theta (n^2)$ συγκρίσεις. Σωστό — αλλά αργό.

Μία διάσταση: ένα εύκολο $O(n\log n)$

Πριν επιτεθούμε στο επίπεδο, ας ζεσταθούμε με την εύκολη εκδοχή: όλα τα σημεία πάνω σε μία ευθεία, μία μόνο συντεταγμένη. Η λύση είναι σχεδόν τετριμμένη:

1. Ταξινόμησε τα σημεία — $O(n\log n)$.
2. Σε ένα γραμμικό πέρασμα, βρες το ελάχιστο της διαφοράς γειτονικών σημείων — $O(n)$.

Γιατί αρκούν τα γειτονικά; Φαντάσου ότι το κοντινότερο ζευγάρι ήταν δύο σημεία ($p$, $q$) που δεν είναι γειτονικά στην ταξινόμηση — άρα ανάμεσά τους κάθεται κάποιο τρίτο σημείο $r$. Τότε όμως το $r$ είναι πιο κοντά σε καθένα τους από όσο είναι το ένα στο άλλο, αφού η ευθεία δεν αφήνει «δίαυλο» να γλιτώσουν. Αντίφαση. Άρα το κοντινότερο ζευγάρι πρέπει να είναι γειτονικό — και η σάρωση γειτονικών αρκεί.

Γιατί δεν δουλεύει το ίδιο τρικ σε 2D; Δοκίμασέ το στο διπλό πάνελ παρακάτω. Στο 1D tab η σάρωση γειτονικών βρίσκει σωστά το κοντινότερο ζευγάρι. Στο 2D tab, ταξινομούμε κατά $x$ και σαρώνουμε — αλλά το κοντινότερο ζευγάρι αποδεικνύεται όχι γειτονικό στην x-ταξινόμηση, και ο γραμμικός αλγόριθμος το χάνει:

Η μία διάσταση δεν μας σώζει στο επίπεδο — το «τρίτο σημείο ανάμεσα» μπορεί να βρίσκεται πολύ μακριά στον $y$ και να μη βοηθάει. Χρειαζόμαστε γνήσια δισδιάστατη ιδέα.

Πρώτη απόπειρα διαίρεσης — και γιατί αποτυγχάνει

Η πρώτη σκέψη: αφού το επίπεδο είναι δισδιάστατο, ας το σπάσουμε σε 4 τεταρτημόρια και ας λύσουμε αναδρομικά σε καθένα.

Μοιάζει «δίκαιο», αλλά κανείς δεν εγγυάται ότι το κάθε τεταρτημόριο θα έχει περίπου $n/4$ σημεία. Δοκίμασε τα τέσσερα σενάρια στο πάνελ παρακάτω: όσο η κατανομή στρέφεται πάνω-δεξιά, οι αναδρομικές κλήσεις γίνονται όλο και πιο ασύμμετρες. Στο τελευταίο σενάριο, όλα τα $n$ σημεία πέφτουν στο ίδιο τεταρτημόριο — η αναδρομή δέχεται ξανά $n$ σημεία και δεν μικραίνει ποτέ.

Στο δεξί πάνελ βλέπεις ήδη τη λύση που θα δουλέψουμε: η κάθετη γραμμή στην κατά $x$ διάμεσο ισορροπεί πάντα τα δύο μισά $n/2+n/2$, ό,τι κι αν είναι τα σημεία.

Σωστή διαίρεση: κάθετη γραμμή στη διάμεσο

Η λύση: αντί για σταθερά όρια, σχεδιάζουμε μια κάθετη γραμμή $L$ ακριβώς στην κατά $x$ διάμεσο των σημείων. Η διάμεσος είναι, εξ ορισμού, η τιμή που αφήνει τα μισά σημεία αριστερά και τα μισά δεξιά — οπότε έχουμε εγγυημένα $\lfloor n/2\rfloor$ σημεία αριστερά και $\lceil n/2\rceil$ δεξιά, ό,τι κι αν είναι τα δεδομένα.

Με τη γραμμή $L$ στη θέση της, το σχήμα D&C ξετυλίγεται σε τρία βήματα. Πάτα Επόμενο για να το ζήσεις βήμα-βήμα — και το Νέο στιγμιότυπο για να δεις ότι δουλεύει σε οποιαδήποτε διάταξη:

Σε λέξεις:

• Διαίρει. Βρες την κατά $x$ διάμεσο (γίνεται σε $O(n)$ — θα δούμε πώς στο L10). Η γραμμή $L$ χωρίζει τα σημεία σε αριστερό σύνολο $P_L$ και δεξί $P_R$.
• Κυρίευσε. Κάλεσε αναδρομικά τον εαυτό σου: ${\delta }_1=\text{ClosestPair}(P_L)$ και ${\delta }_2=\text{ClosestPair}(P_R)$. Θέσε $\delta =\min ({\delta }_1,{\delta }_2)$.
• Συνδύασε. Εδώ κρύβεται η δυσκολία.

Το $\delta$ είναι η μικρότερη απόσταση μέσα σε κάθε πλευρά. Αλλά το κοντινότερο ζευγάρι ολόκληρου του προβλήματος μπορεί να είναι μικτό: ένα σημείο αριστερά, ένα δεξιά. Αυτά τα μικτά ζευγάρια η αναδρομή δεν τα έχει δει ποτέ — πρέπει να τα ελέγξουμε εμείς, στο combine.

Το τέχνασμα της ζώνης (strip)

Αφελώς, τα μικτά ζευγάρια είναι $\frac{n}{2}\cdot \frac{n}{2}=\Theta (n^2)$ — αν τα ελέγξουμε όλα, χάσαμε το παιχνίδι. Χρειαζόμαστε μια παρατήρηση που να πετάει τα περισσότερα.

Σύρε το σημείο $p$ παρακάτω για να δεις την παρατήρηση γεωμετρικά. Ο δίσκος εμβέλειας ακτίνας $\delta$ γύρω από το $p$ δείχνει «πού μπορεί να κρύβεται ένας σύντροφος σε απόσταση $<\delta$». Όσο το $p$ είναι μέσα στη ζώνη, ο δίσκος ξεπερνά τη $L$ και ίσως πιάσει αριστερά σημεία. Μόλις το $p$ απομακρυνθεί περισσότερο από $\delta$ από τη $L$, ο δίσκος δεν φτάνει ποτέ την $L$ — και κανένα αριστερό σημείο δεν μπορεί να είναι σε απόσταση $<\delta$, ό,τι $y$ κι αν έχει:

Άρα κόβουμε κάθε σημείο που απέχει περισσότερο από $\delta$ από τη $L$. Αυτό που μένει είναι μια λεπτή ζώνη πλάτους $2\delta$ γύρω από τη γραμμή. Μόνο μέσα εκεί μπορεί να κρύβεται κοντινότερο μικτό ζευγάρι.

Ωραία — αλλά στη χείριστη περίπτωση όλα τα σημεία μπορεί να πέσουν μέσα στη ζώνη. Δεν μπορούμε λοιπόν να βασιστούμε σε «λίγα σημεία στη ζώνη». Χρειαζόμαστε κάτι πιο δυνατό.

Γιατί αρκεί σταθερό πλήθος γειτόνων

Ωραία — αλλά στη χείριστη περίπτωση όλα τα σημεία μπορεί να πέσουν μέσα στη ζώνη. Δεν μπορούμε λοιπόν να βασιστούμε σε «λίγα σημεία στη ζώνη». Χρειαζόμαστε κάτι πιο δυνατό.

Η ιδέα: ταξινομούμε τα σημεία της ζώνης κατά $y$, και αποδεικνύουμε ότι κάθε σημείο χρειάζεται να συγκριθεί μόνο με τους επόμενους 11 στην ταξινόμηση — όχι με όλα.

Η απόδειξη είναι ένα όμορφο επιχείρημα αραιότητας: τα σημεία δεν στριμώχνονται μέσα στη ζώνη — αλλιώς η αναδρομή θα είχε ήδη βρει απόσταση μικρότερη από $\delta$, αντίφαση. Χωρίζουμε τη ζώνη σε κουτιά $\frac{\delta }{2}\times \frac{\delta }{2}$ — δηλαδή 4 στήλες (2 αριστερά της $L$, 2 δεξιά) και όσες σειρές χρειαζόμαστε. Δύο γεωμετρικά γεγονότα κάνουν τη δουλειά:

Συνδυάζοντας τα δύο: σε 3 διαδοχικές σειρές × 4 στήλες = 12 κουτιά × ≤ 1 σημείο = το πολύ 12 σημεία. Άρα αν δύο σημεία απέχουν $\ge 12$ θέσεις στην ταξινόμηση κατά $y$, είναι υποχρεωτικά σε διαφορετικές «τριάδες σειρών» — οπότε η κατακόρυφη απόστασή τους και μόνο φτάνει το $\delta$. $■$

Δες τώρα τη σάρωση ζωντανά. Πάτα Επόμενο για να σαρώσεις τα σημεία της ζώνης κατά $y$ — και πρόσεξε ότι το «παράθυρο ελέγχου» κάθε σημείου παραμένει πάντα μικρό, όσα σημεία κι αν έχει η ζώνη:

Ο αλγόριθμος

Πολυπλοκότητα

Πρώτη εκδοχή: $O(n{\log }^{2}n)$

Ας μετρήσουμε τη δουλειά μιας αναδρομικής κλήσης σε $n$ σημεία:

• Εύρεση διαμέσου: $O(n)$.
• Δύο αναδρομικές κλήσεις: $2T(n/2)$.
• Φιλτράρισμα της ζώνης και ταξινόμηση κατά $y$: $O(n\log n)$.
• Σάρωση της ζώνης με 11 γείτονες ανά σημείο: $O(n)$.

Άρα:

$T(n)=2T(n/2)+O(n\log n)$

Πρόσεξε: το κόστος συνδυασμού είναι $O(n\log n)$, που δεν είναι της μορφής $O(n^d)$ — οπότε η απλή μορφή του Master Theorem από το L03 δεν εφαρμόζεται απευθείας. Με δέντρο αναδρομής (ή τη γενική μορφή) προκύπτει:

$T(n)=O(n{\log }^{2}n)$

Καλύτερο από το $O(n^2)$ — αλλά όχι ακόμα ο στόχος μας.

Βελτίωση σε $O(n\log n)$

Από πού ήρθε το ενοχλητικό επιπλέον $\log n$; Από τη φράση «ταξινόμηση κατά $y$» — που την κάναμε μέσα σε κάθε αναδρομική κλήση. Αλλά τα σημεία δεν αλλάζουν· γιατί να τα ξανα-ταξινομούμε διαρκώς;

Στο διπλό πάνελ παρακάτω βλέπεις τι κερδίζουμε επίπεδο προς επίπεδο. Με τη «ταξινόμηση μέσα στην κλήση», κάθε επίπεδο κάνει $n\log (n/2^i)$ δουλειά — ένα τρίγωνο που βαραίνει στα πάνω επίπεδα. Με την προταξινόμηση, κάθε επίπεδο κάνει σταθερά $n$ — ένα επίπεδο ορθογώνιο. Άλλαξε το $n$ και πρόσεξε ότι ο λόγος των δύο συνολικών μεγαλώνει σαν $\log n$:

Με αυτή την προταξινόμηση, κάθε κλήση κάνει μόνο γραμμική δουλειά πέρα από τις αναδρομές, και η αναδρομή γίνεται:

$T(n)=2T(n/2)+O(n)$

Master Theorem με $a=2,b=2,d=1$: αφού ${\log }_{2}2=1=d$, περίπτωση 2 → $T(n)=O(n\log n)$. Προσθέτοντας το $O(n\log n)$ της μίας αρχικής ταξινόμησης, η συνολική πολυπλοκότητα παραμένει:

$T(n)=O(n\log n)$

Άσκηση: η κορυφή του βουνού

Το PDF κλείνει με μια κλασική άσκηση D&C — δοκίμασέ τη μόνος σου πριν δεις τη λύση.

Πρόβλημα. Δίνεται πίνακας $A$ μεγέθους $n$ με την εξής ιδιότητα: υπάρχει θέση $i$ τέτοια ώστε $A[1]<A[2]<\cdots <A[i]\text{και}A[i]>A[i+1]>\cdots >A[n].$ Δηλαδή ο πίνακας ανεβαίνει μέχρι μια «κορυφή» και μετά κατεβαίνει (είναι μονότροπος). Δώσε αλγόριθμο που εντοπίζει τη θέση $i$ της κορυφής σε χρόνο $O(\log n)$.

Δοκίμασέ τον πρώτα μόνος. Στο διάγραμμα παρακάτω πάτα «Επόμενο» και πρόσεξε ότι κάθε σύγκριση πετάει ολόκληρο το μισό του πίνακα. Σε $\lceil {\log }_{2}15\rceil =4$ βήματα ο αλγόριθμος βρίσκει την κορυφή, όπου κι αν είναι:

Κλείδωσε τη γνώση

Πρώτα η σκελετική δομή του Closest-Pair — βάλε τα βήματα στη σειρά:

Τώρα το τέχνασμα της ζώνης σε λέξεις — συμπλήρωσε τα κενά:

Μοτίβο σκέψης