Monotone Chain (Κυρτή Θήκη)

Ο αλγόριθμος Monotone Chain είναι ένας αλγόριθμος εύρεσης της κυρτής θήκης (convex hull) ενός συνόλου σημείων στο επίπεδο. Το πετυχαίνει αυτό βρίσκοντας την άνω κυρτή θήκη και την κάτω κυρτή θήκη και ενώνοντάς τες.

• Ορισμός
  • Άνω και κάτω κυρτή θήκη
• Εύρεση άνω και κάτω κυρτής θήκης
• Εύρεση κυρτής θήκης

Ορισμός

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

Σημεία	Κυρτή θήκη

Άνω και κάτω κυρτή θήκη

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

Σημεία	Άνω κυρτή θήκη

Αντίστοιχα, ορίζουμε την κάτω κυρτή θήκη ενός συνόλου σημείων στο επίπεδο ως την τεθλασμένη γραμμή με την ελάχιστη απόσταση από όλα τα σημεία, τέτοια ώστε να μην υπάρχει σημείο το οποίο να έχει μεγαλύτερη τεταγμένη από την τεταγμένη της γραμμής στην ίδια τετμημένη. Όπως και πριν, για ευκολία στον αλγόριθμο που θα ορίσουμε παρακάτω, θεωρούμε ότι εάν υπάρχουν παραπάνω από ένα σημεία με ελάχιστη τετμημένη (και διαφορετική τεταγμένη), τότε η κάτω κυρτή θήκη περιέχει μόνο τη σημείο με την ελάχιστη τεταγμένη από αυτά τα σημεία. Για παράδειγμα, στα ίδια σημεία έχουμε:

Σημεία	Κάτω κυρτή θήκη

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

Σημεία	Άνω κυρτή θήκη	Κάτω κυρτή θήκη	Κυρτή θήκη

Συνεπώς το πρόβλημα της εύρεσης της κυρτής θήκης ενός συνόλου σημείων ανάγεται στην εύρεση της άνω και της κάτω κυρτής θήκης.

Εύρεση άνω και κάτω κυρτής θήκης

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

1. Σε μια άδεια στοίβα (stack) προσθέτουμε το $i$-οστό στοιχείο του πίνακα (αρχικά αυτό είναι το πρώτο στοιχείο)
2. Εάν η στοίβα περιέχει παραπάνω από δύο στοιχεία, ελέγχουμε εάν τα τρία τελευταία στοιχεία στρέφουν δεξιόστροφα (με τη χρήση του CCW). Εάν δεν στρέφουν δεξιόστροφα, τότε αφαιρούμε το προτελευταίο στοιχείο από τη στοίβα και επαναλαμβάνουμε αυτό το βήμα
3. Εάν το $i$-οστό στοιχείο δεν είναι το τελευταίο στοιχείο του πίνακα, τότε αυξάνουμε το $i$ και επιστρέφουμε στο βήμα 1

Ακολουθεί η υλοποίηση του κώδικα που μόλις περιγράψαμε σε c++.

sort(pt+1, pt+N+1);
int top=0;
for(int i=1; i<=N; ++i) {
    while(top>=2 && CCW(pt[hull[top-1]], pt[hull[top]], pt[i])>=0) {
        --top;
    }
    hull[++top]=i;
}

Όπου N είναι το πλήθος των σημείων, pt ο πίνακας που περιέχει τα σημεία, και hull ένας πίνακας που είναι αρχικά άδειος και λειτουργεί σαν στοίβα.

Για την κάτω κυρτή θήκη ο αλγόριθμος είναι πανομοιότυπος. Αφού ταξινομήσουμε τα σημεία πρώτα ως προς τετμημένη και έπειτα ως προς τεταγμένη, ακολουθούμε τα εξής βήματα:

1. Σε μια άδεια στοίβα προσθέτουμε το $i$-οστό στοιχείο του πίνακα
2. Εάν η στοίβα περιέχει παραπάνω από δύο στοιχεία, ελέγχουμε εάν τα τρία τελευταία στοιχεία στρέφουν αριστερόστροφα. Εάν δεν στρέφουν αριστερόστροφα, τότε αφαιρούμε το προτελευταίο στοιχείο από τη στοίβα και επαναλαμβάνουμε αυτό το βήμα
3. Εάν το $i$-οστό στοιχείο δεν είναι το τελευταίο στοιχείο του πίνακα, τότε αυξάνουμε το $i$ και επιστρέφουμε στο βήμα 1

Ακολουθεί η υλοποίηση σε c++.

sort(pt+1, pt+N+1);
int top=0;    
for(int i=1; i<=N; ++i) {
    while(top>=2 && CCW(pt[hull[top-1]], pt[hull[top]], pt[i])>=0) {
        --top;
    }
    hull[++top]=i;
}

Εύρεση κυρτής θήκης

Αφού είδαμε ότι η κυρτή θήκη είναι η ένωση της άνω και της κάτω κυρτής θήκης, ουσιαστικά ο αλγόριθμος είναι ο συνδυασμός των δύο παραπάνω αλγορίθμων. Θα κάνουμε όμως μερικές μικροαλλαγές για να διευκολυνθούμε στο γράψιμο.

Κατ’αρχάς δεν χρειάζεται να ταξινομήσουμε τον πίνακα των σημείων δεύτερη φορά. Επίσης, βολεύει να χρησιμοποιούμε την ίδια στοίβα και να μην δημιουργούμε καινούρια όταν βρίσκουμε την κάτω κυρτή θήκη. Τέλος, για να έχουμε τα σημεία σε κάποια σειρά, θα βρούμε ανάποδα την κάτω κυρτή θήκη, ξεκινώντας από το N-1 και κατεβαίνοντας. Ο λόγος που ξεκινάμε από το N-1 είναι για να μην έχουμε δύο φορές το τελευταίο στοιχείο. Οπότε ο κώδικας γίνεται ως εξής:

sort(pt+1, pt+N+1);
int top=0;
for(int i=1; i<=N; ++i) { // Υπολογισμός της άνω κυρτής θήκης
    while(top>=2 && CCW(pt[hull[top-1]], pt[hull[top]], pt[i])>=0) {
        --top;
    }
    hull[++top]=i;
}
for(int i=N-1; i>=1; --i) { // Υπολογισμός της κάτω κυρτής θήκης
    while(top>=2 && CCW(pt[hull[top-1]], pt[hull[top]], pt[i])>=0) {
        --top;
    }
    hull[++top]=i;
}
--top;

Προσοχή πως θέλουμε να συμπεριλάβουμε το 1ο στοιχείο στην κάτω κυρτή θήκη γιατί μπορεί να αφαιρέσει σημεία με την προσθήκη του. Στο τέλος όμως το αφαιρούμε για να μην υπάρχει δύο φορές. Μπορείτε να βρείτε πληρέστερη υλοποίηση του αλγορίθμου Monotone Chain εδώ.

Σχόλια