Optimal tetrahedralization of the 3D-region between a convex polyhedron and a convex polygon
Φόρτωση...
Ημερομηνία
Συγγραφείς
Palios, Leonidas
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Computational Geometry
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Given a convex polyhedron P and a convex polygon Q in R3 such that Q?s supporting plane does not intersect P, we are interested in tetrahedralizing the closure of the difference convex_hull(P ? Q) ? P; since P is convex, this difference is a connected nonconvex subset of R3 which we call the region between P and Q. The problem is motivated by the work of Bern on tetrahedralizing the region between convex polyhedra (Bern, 1993). In this paper, we describe a novel approach that yields an optimal tetrahedralization, that is, O(n) tetrahedra and no Steiner points; the tetrahedralization is compatible with the boundary of the polyhedron P, and can be computed in optimal O(n) time. Our result also implies a simple and optimal algorithm for the side-by-side case (Bern, 1993) when Steiner points are allowed: the region between two non-intersecting convex polyhedra of total size n can be partitioned into O(n) tetrahedra using O(n) Steiner points; as above, the tetrahedralization is compatible with the boundaries of the two polyhedra, and can be computed in O(n) time. Note that if Steiner points are not allowed, instances of side-by-side convex polyhedra lead to tetrahedralizations quadratic in their sizes.
Περιγραφή
Λέξεις-κλειδιά
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής