Καμπύλη Χίλμπερτ

Η καμπύλη Χίλμπερτ (επίσης γνωστή ως καμπύλη πλήρωσης χώρου Χίλμπερτ) είναι μια συνεχής κλασματική καμπύλη πλήρωσης χώρου που περιγράφηκε για πρώτη φορά από τον Γερμανό μαθηματικό Ντάβιντ Χίλμπερτ το 1891,^[1] ως παραλλαγή των καμπυλών πλήρωσης χώρου του Πεάνο που ανακαλύφθηκαν από τον Τζουζέπε Πεάνο το 1890^[2].

Επειδή είναι χωροπληρωτική, η διάσταση Χάουσντορφ της είναι 2 (ακριβώς, η εικόνα της είναι το μοναδιαίο τετράγωνο, του οποίου η διάσταση είναι 2 σε οποιονδήποτε ορισμό της διάστασης- η γραφική της παράσταση είναι ένα συμπαγές σύνολο ομοιομορφικό με το κλειστό μοναδιαίο διάστημα, με διάσταση Χάουσντορφ 2).

Η καμπύλη Χίλμπερτ κατασκευάζεται ως όριο γραμμικών καμπυλών. Το μήκος της $n$ thς καμπύλης είναι $\textstyle 2^{n}-{1 \over 2^{n}}$ , δηλαδή το μήκος αυξάνεται εκθετικά με το $n$ , παρόλο που κάθε καμπύλη περιέχεται σε ένα τετράγωνο με εμβαδόν $1$ .

Εικόνες

Καμπύλη Χίλμπερτ, πρώτης τάξεως
Καμπύλες Χίλμπερτ, πρώτης και δεύτερης τάξεως
Καμπύλες Χίλμπερτ, πρώτης έως τρίτης τάξεως
Κανόνες παραγωγής
Καμπύλη Χίλμπερτ, κατασκευή με χρωματική κωδικοποίηση
Μια τρισδιάστατη καμπύλη Χίλμπερτ με χρώμα που δείχνει την εξέλιξη
Παραλλαγή, τρεις πρώτες επαναλήψεις^[3]

Εφαρμογές και αλγόριθμοι χαρτογράφησης

Τόσο η πραγματική καμπύλη Χίλμπερτ όσο και οι διακριτές προσεγγίσεις της είναι χρήσιμες επειδή δίνουν μια αντιστοιχία μεταξύ του 1D χώρου και του 2D χώρου που διατηρεί αρκετά καλά την τοπικότητα^[4], πράγμα που σημαίνει ότι δύο σημεία δεδομένων που βρίσκονται κοντά το ένα στο άλλο στον μονοδιάστατο χώρο βρίσκονται επίσης κοντά το ένα στο άλλο μετά την αναδίπλωση. Το αντίστροφο δεν ισχύει πάντα.

Λόγω αυτής της ιδιότητας τοπικότητας, η καμπύλη Χίλμπερτ χρησιμοποιείται ευρέως στην πληροφορική. Για παράδειγμα, το εύρος των διευθύνσεων IP που χρησιμοποιούνται από υπολογιστές μπορεί να αναπαρασταθεί σε μια εικόνα χρησιμοποιώντας την καμπύλη Χίλμπερτ. Ο κώδικας που παράγει την εικόνα πρέπει να μεταβεί από 2D σε 1D για να βρει το χρώμα κάθε εικονοστοιχείου και η καμπύλη Χίλμπερτ χρησιμοποιείται μερικές φορές επειδή διατηρεί τις διευθύνσεις IP κοντά μεταξύ τους στην εικόνα^[5]. Η ιδιότητα της τοπικότητας της καμπύλης Χίλμπερτ έχει επίσης χρησιμοποιηθεί για τον σχεδιασμό αλγορίθμων για την εξερεύνηση περιοχών από κινητά ρομπότ^[6]^[7].

Σε έναν αλγόριθμο που ονομάζεται Riemersma dithering, η φωτογραφία σε κλίμακα του γκρι μπορεί να μετατραπεί σε ασπρόμαυρη εικόνα με χρήση κατωφλίου, με το ποσό που απομένει από κάθε εικονοστοιχείο να προστίθεται στο επόμενο εικονοστοιχείο κατά μήκος της καμπύλης Χίλμπερτ. Ο κώδικας για να γίνει αυτό θα αντιστοιχούσε από 1D σε 2D, και η καμπύλη Χίλμπερτ χρησιμοποιείται μερικές φορές επειδή δεν δημιουργεί τα ενοχλητικά μοτίβα που θα ήταν ορατά στο μάτι αν η σειρά ήταν απλά από αριστερά προς τα δεξιά σε κάθε σειρά εικονοστοιχείων^[8]. οι καμπύλες Χίλμπερτ σε υψηλότερες διαστάσεις αποτελούν μια περίπτωση γενίκευσης των κωδίκων του γκρι (Gray), και χρησιμοποιούνται μερικές φορές για παρόμοιους σκοπούς, για παρόμοιους λόγους. Για πολυδιάστατες βάσεις δεδομένων, έχει προταθεί να χρησιμοποιείται η τάξη Χίλμπερτ αντί της τάξης Ζ, επειδή έχει καλύτερη συμπεριφορά διατήρησης της τοπικότητας. Για παράδειγμα, οι καμπύλες Χίλμπερτ έχουν χρησιμοποιηθεί για τη συμπίεση και επιτάχυνση των ευρετηρίων R-tree^[9] (βλέπε δέντρο Χίλμπερτ R-tree). Έχουν επίσης χρησιμοποιηθεί για να βοηθήσουν στη συμπίεση αποθηκών δεδομένων^[10]^[11].

Λαμβάνοντας υπόψιν την ποικιλομορφία των εφαρμογών, είναι χρήσιμο να υπάρχουν αλγόριθμοι που μπορούν να δημιουργήσουν αντιστοιχίες και προς τις δύο κατευθύνσεις. Σε πολλές γλώσσες, αυτοί οι αλγόριθμοι είναι πιο αποδοτικοί αν υλοποιούνται με χρήση επανάληψης αντί για αναδρομή. Ο ακόλουθος κώδικας C εκτελεί αντιστοίχιση δύο κατευθύνσεων, χρησιμοποιώντας επανάληψη και πράξεις bit αντί για αναδρομή. Υποθέτει ένα τετράγωνο χωρισμένο σε n επί n κελιά, για n μια δύναμη του 2, με ακέραιες συντεταγμένες, με (0,0) στην κάτω αριστερή γωνία, (n − 1, n − 1) στην πάνω δεξιά γωνία, και μια απόσταση d που ξεκινά από το 0 στην κάτω αριστερή γωνία και φτάνει μέχρι το $n^{2}-1$ στην κάτω δεξιά γωνία. Αυτό είναι διαφορετικό από το κινούμενο σχέδιο που παρουσιάστηκε παραπάνω, όπου η καμπύλη ξεκινάει στην επάνω αριστερή γωνία και καταλήγει στην επάνω δεξιά γωνία.

//convert (x,y) to d
int xy2d (int n, int x, int y) {
    int rx, ry, s, d=0;
    for (s=n/2; s>0; s/=2) {
        rx = (x & s) > 0;
        ry = (y & s) > 0;
        d += s * s * ((3 * rx) ^ ry);
        rot(n, &x, &y, rx, ry);
    }
    return d;
}

//convert d to (x,y)
void d2xy(int n, int d, int *x, int *y) {
    int rx, ry, s, t=d;
    *x = *y = 0;
    for (s=1; s<n; s*=2) {
        rx = 1 & (t/2);
        ry = 1 & (t ^ rx);
        rot(s, x, y, rx, ry);
        *x += s * rx;
        *y += s * ry;
        t /= 4;
    }
}

//rotate/flip a quadrant appropriately
void rot(int n, int *x, int *y, int rx, int ry) {
    if (ry == 0) {
        if (rx == 1) {
            *x = n-1 - *x;
            *y = n-1 - *y;
        }

        //Swap x and y
        int t  = *x;
        *x = *y;
        *y = t;
    }
}

Αυτές χρησιμοποιούν τις συμβάσεις της C: το σύμβολο & είναι ένα bitwise AND, το σύμβολο ^ είναι ένα bitwise XOR, το += είναι ο τελεστής πρόσθεσης/ανάθεσης (x += y είναι ισοδύναμο με x = x + y) και το /= είναι ο τελεστής διαίρεσης/ανάθεσης. Ο χειρισμός των booleans στη C σημαίνει ότι στο xy2d, η μεταβλητή rx τίθεται σε 0 ή 1 για να ταιριάζει με το bit s του x, και ομοίως για το ry.

Η συνάρτηση xy2d λειτουργεί από πάνω προς τα κάτω, ξεκινώντας με τα πιο σημαντικά bits των x και y και χτίζοντας πρώτα τα πιο σημαντικά bits του d. Η συνάρτηση d2xy λειτουργεί με την αντίθετη σειρά, ξεκινώντας με τα λιγότερο σημαντικά bits του d και αναπτύσσοντας τα x και y ξεκινώντας από τα λιγότερο σημαντικά bits. Και οι δύο συναρτήσεις χρησιμοποιούν τη συνάρτηση rotation για την κατάλληλη περιστροφή και αναστροφή του συστήματος συντεταγμένων (x,y).

Οι δύο αλγόριθμοι χαρτογράφησης λειτουργούν με παρόμοιο τρόπο. Ολόκληρο το τετράγωνο θεωρείται ότι αποτελείται από 4 περιοχές, διατεταγμένες 2 προς 2. Κάθε περιοχή αποτελείται από 4 μικρότερες περιοχές, και ούτω καθεξής, για έναν αριθμό επιπέδων. Στο επίπεδο s, κάθε περιοχή αποτελείται από s επί s κελιά. Υπάρχει ένας μόνο βρόχος FOR που επαναλαμβάνει τα επίπεδα. Σε κάθε επανάληψη, ένα ποσό προστίθεται στο d ή στα x και y, που καθορίζεται από το σε ποια από τις 4 περιοχές βρίσκεται στο τρέχον επίπεδο. Η τρέχουσα περιοχή από τις 4 είναι (rx,ry), όπου rx και ry είναι το καθένα 0 ή 1. Έτσι καταναλώνει 2 bits εισόδου, (είτε 2 από το d είτε από 1 το καθένα από τα x και y), και παράγει δύο bits εξόδου. Καλεί επίσης τη συνάρτηση περιστροφής, έτσι ώστε τα (x,y) να είναι κατάλληλα για το επόμενο επίπεδο, στην επόμενη επανάληψη. Για το xy2d, ξεκινάει από το ανώτερο επίπεδο ολόκληρου του τετραγώνου, και κατεβαίνει μέχρι το κατώτερο επίπεδο των μεμονωμένων κελιών. Για το d2xy, ξεκινάει από το κατώτερο επίπεδο με τα κελιά, και εργάζεται προς τα πάνω για να συμπεριλάβει ολόκληρο το τετράγωνο.

Υπάρχει η δυνατότητα να υλοποιηθούν αποτελεσματικά οι καμπύλες Χίλμπερτ ακόμη και όταν ο χώρος δεδομένων δεν σχηματίζει τετράγωνο.^[12].Επιπλέον, υπάρχουν αρκετές πιθανές γενικεύσεις των καμπυλών Χίλμπερτ σε υψηλότερες διαστάσεις^[13]^[14].

Αναπαράσταση ως σύστημα Λιντενμάγιερ

Καμπύλη Χίλμπερτ στην έκτη επανάληψή της

Η καμπύλη Χίλμπερτ μπορεί να εκφραστεί με ένα σύστημα επανεγγραφής (L-system - (σύστημα L).

Αλφάβητο : A, B

Σταθερές : F + -

Αξίωμα : A

Κανόνες παραγωγής:

A → +BF−AFA−FB+

B → −AF+BFB+FA−

Εδώ, το "F" σημαίνει "σχεδίαση προς τα εμπρός", το "+" σημαίνει "στροφή αριστερά 90°", το "-" σημαίνει "στροφή δεξιά 90°" (βλ. γραφικά χελώνας) και τα "A" και "B" αγνοούνται κατά τη σχεδίαση.

Άλλες υλοποιήσεις

Το Graphics Gems II^[15] συζητά τη συνοχή των καμπυλών Χίλμπερτ και παρέχει υλοποίηση.

Η καμπύλη Χίλμπερτ χρησιμοποιείται συνήθως μεταξύ της απόδοσης εικόνων ή βίντεο. Κοινά προγράμματα όπως το Μπλέντερ και το Σινεμά 4D χρησιμοποιούν την καμπύλη Χίλμπερτ για την ανίχνευση των αντικειμένων και την απόδοση της σκηνής.

Δείτε επίσης

Βιβλιογραφία

Warren Jr., Henry S. (2013). Hacker's Delight (2 έκδοση). Addison Wesley – Pearson Education, Inc. ISBN 978-0-321-84268-8.
McKenna, Douglas M. (2019). Hilbert Curves: Outside-In and Inside-Gone. Mathemaesthetics, Inc. ISBN 978-1-7332188-0-1.

Παραπομπές

↑ D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460.
↑ G.Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157–160.
↑ Bourges, Pascale. "Chapitre 1: fractales", Fractales et chaos. Accessed: 9 February 2019.
↑ Moon, B.; Jagadish, H.V.; Faloutsos, C.; Saltz, J.H. (2001), «Analysis of the clustering properties of the Hilbert space-filling curve», IEEE Transactions on Knowledge and Data Engineering 13 (1): 124–141, doi:10.1109/69.908985 .
↑ «Mapping the whole internet with Hilbert curves». blog.benjojo.co.uk. Ανακτήθηκε στις 2 Ιανουαρίου 2021.
↑ Spires, Shannon V.; Goldsmith, Steven Y. (1998), Drogoul, Alexis; Tambe, Milind; Fukuda, Toshio, επιμ., Exhaustive geographic search with mobile robots along space-filling curves, 1456, Berlin, Heidelberg: Springer Berlin Heidelberg, σελ. 1–12, doi:10.1007/bfb0033369, ISBN 978-3-540-64768-3, http://link.springer.com/10.1007/BFb0033369, ανακτήθηκε στις 2023-08-14
↑ Sadat, Seyed Abbas; Wawerla, Jens; Vaughan, Richard (2015). «Fractal trajectories for online non-uniform aerial coverage». 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 2971–2976.
↑ Thiadmer Riemersma (1998-12-01). «A Balanced Dithering Technique». C/C++ User's Journal (Dr. Dobb's). https://www.drdobbs.com/a-balanced-dithering-technique/184403590.
↑ I. Kamel, C. Faloutsos, Hilbert R-tree: An improved R-tree using fractals, in: Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1994, pp. 500–509.
↑ Eavis, T.· Cueva, D. (2007). «A Hilbert Space Compression Architecture for Data Warehouse Environments». Data Warehousing and Knowledge Discovery. Lecture Notes in Computer Science. 4654. σελίδες 1–12. doi:10.1007/978-3-540-74553-2_1. ISBN 978-3-540-74552-5.
↑ Lemire, Daniel; Kaser, Owen (2011). «Reordering Columns for Smaller Indexes». Information Sciences 181 (12): 2550–2570. doi:10.1016/j.ins.2011.02.002.
↑ Hamilton, C. H.; Rau-Chaplin, A. (2007). «Compact Hilbert indices: Space-filling curves for domains with unequal side lengths». Information Processing Letters 105 (5): 155–163. doi:10.1016/j.ipl.2007.08.034.
↑ Alber, J.; Niedermeier, R. (2000). «On multidimensional curves with Hilbert property». Theory of Computing Systems 33 (4): 295–312. doi:10.1007/s002240010003.
↑ H. J. Haverkort, F. van Walderveen, Four-dimensional Hilbert curves for R-trees, in: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73.
↑ Voorhies, Douglas: Space-Filling Curves and a Measure of Coherence, pp. 26–30, Graphics Gems II.

[1] D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460.

[2] G.Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157–160.

[3] Bourges, Pascale. "Chapitre 1: fractales", Fractales et chaos. Accessed: 9 February 2019.

[4] Moon, B.; Jagadish, H.V.; Faloutsos, C.; Saltz, J.H. (2001), «Analysis of the clustering properties of the Hilbert space-filling curve», IEEE Transactions on Knowledge and Data Engineering 13 (1): 124–141, doi:10.1109/69.908985 .

[5] «Mapping the whole internet with Hilbert curves». blog.benjojo.co.uk. Ανακτήθηκε στις 2 Ιανουαρίου 2021.

[6] Spires, Shannon V.; Goldsmith, Steven Y. (1998), Drogoul, Alexis; Tambe, Milind; Fukuda, Toshio, επιμ., Exhaustive geographic search with mobile robots along space-filling curves, 1456, Berlin, Heidelberg: Springer Berlin Heidelberg, σελ. 1–12, doi:10.1007/bfb0033369, ISBN 978-3-540-64768-3, http://link.springer.com/10.1007/BFb0033369, ανακτήθηκε στις 2023-08-14

[7] Sadat, Seyed Abbas; Wawerla, Jens; Vaughan, Richard (2015). «Fractal trajectories for online non-uniform aerial coverage». 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 2971–2976.

[8] Thiadmer Riemersma (1998-12-01). «A Balanced Dithering Technique». C/C++ User's Journal (Dr. Dobb's). https://www.drdobbs.com/a-balanced-dithering-technique/184403590.

[9] I. Kamel, C. Faloutsos, Hilbert R-tree: An improved R-tree using fractals, in: Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1994, pp. 500–509.

[10] Eavis, T.· Cueva, D. (2007). «A Hilbert Space Compression Architecture for Data Warehouse Environments». Data Warehousing and Knowledge Discovery. Lecture Notes in Computer Science. 4654. σελίδες 1–12. doi:10.1007/978-3-540-74553-2_1. ISBN 978-3-540-74552-5.

[11] Lemire, Daniel; Kaser, Owen (2011). «Reordering Columns for Smaller Indexes». Information Sciences 181 (12): 2550–2570. doi:10.1016/j.ins.2011.02.002.

[12] Hamilton, C. H.; Rau-Chaplin, A. (2007). «Compact Hilbert indices: Space-filling curves for domains with unequal side lengths». Information Processing Letters 105 (5): 155–163. doi:10.1016/j.ipl.2007.08.034.

[13] Alber, J.; Niedermeier, R. (2000). «On multidimensional curves with Hilbert property». Theory of Computing Systems 33 (4): 295–312. doi:10.1007/s002240010003.

[14] H. J. Haverkort, F. van Walderveen, Four-dimensional Hilbert curves for R-trees, in: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73.

[15] Voorhies, Douglas: Space-Filling Curves and a Measure of Coherence, pp. 26–30, Graphics Gems II.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]