Détail de l'auteur
Auteur Gill Barequet |
Documents disponibles écrits par cet auteur (1)
Ajouter le résultat dans votre panier
Visionner les documents numériques
Affiner la recherche Interroger des sources externes
Titre : Straight skeletons of three-dimensional polyhedra Type de document : Article/Communication Auteurs : Gill Barequet, Auteur ; David Eppstein, Auteur ; Michael T. Goodrich, Auteur ; Amir Vaxman, Auteur Editeur : Ithaca [New York - Etats-Unis] : ArXiv - Université Cornell Année de publication : 2008 Importance : 12 p. Format : 21 x 30 cm Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Algorithmique
[Termes IGN] complexité
[Termes IGN] généralisation
[Termes IGN] polyèdre
[Termes IGN] squelettisation
[Termes IGN] voxelRésumé : (Auteur) This paper studies the straight skeleton of polyhedra in three dimensions. We first address voxel-based polyhedra (polycubes), formed as the union of a collection of cubical (axis-aligned) voxels. We analyze the ways in which the skeleton may intersect each voxel of the polyhedron, and show that the skeleton may be constructed by a simple voxel-sweeping algorithm taking constant time per voxel. In addition, we describe a more complex algorithm for straight skeletons of voxel-based polyhedra, which takes time proportional to the area of the surfaces of the straight skeleton rather than the volume of the polyhedron. We also consider more general polyhedra with axis parallel edges and faces, and show that any n-vertex polyhedron of this type has a straight skeleton with O(n2) features. We provide algorithms for constructing the straight skeleton, with running time O(min(n2 logn;k logO(1) n)) where k is the output complexity. Next, we discuss the straight skeleton of a general non convex polyhedron. We show that it has an ambiguity issue, and suggest a consistent method to resolve it. We prove that the straight skeleton of a general polyhedron has a superquadratic complexity in the worst case. Finally, we report on an implementation of a simple algorithm for the general case. Numéro de notice : P2008-001 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Preprint DOI : 10.48550/arXiv.0805.0022 Date de publication en ligne : 30/04/2008 En ligne : https://doi.org/10.48550/arXiv.0805.0022 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=84165 Documents numériques
en open access
Straight skeletons of three-dimensional polyhedraAdobe Acrobat PDF
