Optimal tetrahedralization of the 3D-region between a convex polyhedron and a convex polygon
| dc.contributor.author | Palios, Leonidas | en |
| dc.date.accessioned | 2015-11-24T17:02:51Z | |
| dc.date.available | 2015-11-24T17:02:51Z | |
| dc.identifier.issn | 0925-7721 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11101 | |
| dc.rights | Default Licence | - |
| dc.title | Optimal tetrahedralization of the 3D-region between a convex polyhedron and a convex polygon | en |
| heal.abstract | 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 |
| heal.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.identifier.primary | 10.1016/0925-7721(95)00011-9 | - |
| heal.journalName | Computational Geometry | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 1996 | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Αρχεία
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.74 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: