Δέντρο πλήρωσης χώρου

Τα δέντρα πλήρωσης χώρου είναι γεωμετρικές κατασκευές που είναι ανάλογες με τις καμπύλες που γεμίζουν το χώρο,^[1] αλλά έχουν διακλαδισμένη, δενδροειδή δομή και έχουν ρίζες. Ένα δέντρο πλήρωσης χώρου ορίζεται από μια αυξητική διαδικασία που καταλήγει σε ένα δέντρο για το οποίο κάθε σημείο του χώρου έχει ένα μονοπάτι πεπερασμένου μήκους που συγκλίνει σε αυτό. Σε αντίθεση με τις καμπύλες πλήρωσης χώρου, τα μεμονωμένα μονοπάτια στο δέντρο είναι σύντομα, επιτρέποντας τη γρήγορη πρόσβαση σε οποιοδήποτε μέρος του χώρου από τη ρίζα.^[2]^[3] Τα απλούστερα παραδείγματα δέντρων πλήρωσης χώρου έχουν μια κανονική, αυτοομοιόμορφη, μορφοκλασματική δομή, αλλά μπορούν να γενικευτούν σε μη κανονικές και ακόμη και σε τυχαίες/Μόντε Κάρλο παραλλαγές (βλέπε: Ταχεία εξερεύνηση τυχαίου δέντρου^[4]). Τα δέντρα πλήρωσης χώρου έχουν ενδιαφέροντες παραλληλισμούς στη φύση, συμπεριλαμβανομένων των συστημάτων διανομής υγρών, των αγγειακών δικτύων και της κλασματικής ανάπτυξης των φυτών, και πολλές ενδιαφέρουσες συνδέσεις με τα συστήματα L στην επιστήμη των υπολογιστών.

Ορισμός[Επεξεργασία | επεξεργασία κώδικα]

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

Η έννοια του "δέντρου που γεμίζει το χώρο" με αυτή την έννοια περιγράφεται στο κεφάλαιο 15 του σημαντικού βιβλίου του Μάντελμπροτ με τίτλο The Fractal Geometry of Nature (1982)^[5]. Η έννοια έγινε πιο αυστηρή και της δόθηκε το όνομα "χωροπληκτικό δέντρο" σε μια τεχνική έκθεση του 2009^[6] που ορίζει τις έννοιες "χωροπληκτικό" και "δέντρο" διαφορετικά από τους παραδοσιακούς ορισμούς τους στα μαθηματικά. Όπως εξηγείται στο άρθρο για την καμπύλη που γεμίζει το χώρο, το 1890, ο Πεάνο βρήκε την πρώτη καμπύλη που γεμίζει το χώρο, και σύμφωνα με τον ορισμό του Τζόρνταν από το 1887, ο οποίος είναι πλέον καθιερωμένος, μια καμπύλη είναι μια ενιαία συνάρτηση και όχι μια ακολουθία συναρτήσεων. Η καμπύλη είναι " πλήρωση του χώρου" επειδή είναι "μια καμπύλη της οποίας το εύρος περιλαμβάνει ολόκληρο το δισδιάστατο μοναδιαίο τετράγωνο" (όπως εξηγείται στην πρώτη πρόταση του άρθρου για την καμπύλη πλήρωσης του χώρου).

Ωστόσο, ένα δέντρο πλήρωσης χώρου, όπως ορίζεται στην τεχνική έκθεση, δεν είναι ένα ενιαίο δέντρο. Είναι μόνο μια ακολουθία δέντρων. Το έγγραφο αναφέρει ότι: "Ένα δέντρο πλήρωσης χώρου ορίζεται στην πραγματικότητα ως μια άπειρη ακολουθία δέντρων". Ορίζει το $T_{\text{square}}$ ως μια "ακολουθία δέντρων", και στη συνέχεια δηλώνει ότι " $T_{\text{square}}$ είναι ένα δεντρό που γεμίζει το χώρο". Δεν γεμίζει το χώρο με την τυπική έννοια του να περιλαμβάνει ολόκληρο το δισδιάστατο μοναδιαίο τετράγωνο. Αντ' αυτού, το έγγραφο το ορίζει ως έχον δέντρα στην ακολουθία που έρχονται αυθαίρετα κοντά σε κάθε σημείο. Αναφέρει: "Μια ακολουθία δέντρων T ονομάζεται "πλήρωση χώρου" σε ένα χώρο X εάν για κάθε x ∈ X, υπάρχει ένα μονοπάτι στο δέντρο που ξεκινά από τη ρίζα και συγκλίνει στο x.". Ο συνήθης όρος για την έννοια αυτή είναι ότι περιλαμβάνει ένα σύνολο σημείων που είναι πυκνό παντού στο μοναδιαίο τετράγωνο.

Παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

Το απλούστερο παράδειγμα ενός δέντρου πλήρωσης χώρου είναι αυτό που γεμίζει μια τετραγωνική επίπεδη περιοχή. Οι εικόνες απεικονίζουν την κατασκευή για την επίπεδη περιοχή $[0,1]^{2}\subset \mathbb {R} ^{2}$ . Σε κάθε επανάληψη, προστίθενται πρόσθετα κλαδιά στα υπάρχοντα δέντρα.

Τετράγωνο δέντρο συμπλήρωσης χώρου (Επανάληψη 1)
Τετράγωνο δέντρο συμπλήρωσης χώρου (Επανάληψη 2)
Τετράγωνο δέντρο συμπλήρωσης χώρου (Επανάληψη 3)
Τετράγωνο δέντρο συμπλήρωσης χώρου (Επανάληψη 4)
Τετράγωνο δέντρο συμπλήρωσης χώρου (Επανάληψη 5)
Τετράγωνο δέντρο συμπλήρωσης χώρου (Επανάληψη6)

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

Σχήμα υποδιαίρεσης για τις τρεις πρώτες επαναλήψεις του τριγωνικού δέντρου πλήρωσης χώρου

Οι πρώτες έξι επαναλήψεις του τριγωνικού δέντρου πλήρωσης χώρου απεικονίζονται παρακάτω:

Τριγωνικό δέντρο πλήρωσης χώρου (επανάληψη 1)
Τριγωνικό δέντρο πλήρωσης χώρου (επανάληψη 2)
Τριγωνικό δέντρο πλήρωσης χώρου (επανάληψη 3)
Τριγωνικό δέντρο πλήρωσης χώρου (επανάληψη 4)
Τριγωνικό δέντρο πλήρωσης χώρου (επανάληψη 5)
Τριγωνικό δέντρο πλήρωσης χώρου (επανάληψη 6)

Τα δέντρα πλήρωσης χώρου μπορούν επίσης να κατασκευαστούν σε υψηλότερες διαστάσεις. Τα απλούστερα παραδείγματα είναι οι κύβοι στο $\mathbb {R} ^{3}$ και οι υπερκύβοι στο $\mathbb {R} ^{n}$ . Μια παρόμοια ακολουθία επαναλήψεων που χρησιμοποιήθηκε για το τετράγωνο δέντρο πλήρωσης χώρου μπορεί να χρησιμοποιηθεί για τους υπερκύβους. Η τρίτη επανάληψη ενός τέτοιου δέντρου πλήρωσης χώρου στο $\mathbb {R} ^{3}$ απεικονίζεται παρακάτω:

Δέντρο πλήρωσης χώρου κύβου (επανάληψη 3)

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

H. Sagan. Space-filling curves. — New York: Springer-Verlag, 1994. — (Universitext). — ISBN 0-387-94265-3.
J.J. Kuffner , S.M. LaValle. Space-filling Trees : Технический отчёт. — The Robotics Institute, Carnegie Mellon University,, 2009. — № CMU-RI-TR-09-47.
J.J. Kuffner , S.M. LaValle. Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference. — 2011. — С. 2199—2206.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ Sagan, Hans (2 Σεπτεμβρίου 1994). Space-Filling Curves. Springer New York. ISBN 978-0-387-94265-0.
↑ Kuffner, J. J. and S. M. LaValle: Space-filling Trees, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.
↑ Kuffner, J. J.; LaValle, S.M.; “Space-filling trees: A new perspective on incremental search for motion planning,” Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on , vol., no., pp.2199-2206, 25-30 Sept. 2011
↑ «"Rapidly-exploring random trees: A new tool for path planning" (PDF)» (PDF).
↑ Mandelbrot, Benoît (1982). The Fractal Geometry of Nature. W H Freeman & Co. ISBN 0-7167-1186-9. Αρχειοθετήθηκε από το πρωτότυπο στις 30 Νοεμβρίου 2015.
↑ Kuffner, J. J. and S. M. LaValle: Space-filling Trees, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.

[1] Sagan, Hans (2 Σεπτεμβρίου 1994). Space-Filling Curves. Springer New York. ISBN 978-0-387-94265-0.

[2] Kuffner, J. J. and S. M. LaValle: Space-filling Trees, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.

[3] Kuffner, J. J.; LaValle, S.M.; “Space-filling trees: A new perspective on incremental search for motion planning,” Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on , vol., no., pp.2199-2206, 25-30 Sept. 2011

[4] «"Rapidly-exploring random trees: A new tool for path planning" (PDF)» (PDF).

[5] Mandelbrot, Benoît (1982). The Fractal Geometry of Nature. W H Freeman & Co. ISBN 0-7167-1186-9. Αρχειοθετήθηκε από το πρωτότυπο στις 30 Νοεμβρίου 2015.

[6] Kuffner, J. J. and S. M. LaValle: Space-filling Trees, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.

[1]

[2]

[3]

[4]

[5]

[6]