Přejít k obsahu


Inverted Ball as Noundary-constraint for Voronoi Diagrams of 3D Spheres

Citace: [] MAŇÁK, M., KOLINGEROVÁ, I. Inverted Ball as Noundary-constraint for Voronoi Diagrams of 3D Spheres. Brussels, 2009.
Druh: Zaniklé typy
Jazyk publikace: eng
Anglický název: Inverted Ball as Noundary-constraint for Voronoi Diagrams of 3D Spheres
Rok vydání: 2009
Místo konání: Brussels
Název zdroje: ULB Brussels
Autoři: Mgr. Martin Maňák , Doc. Dr. Ing. Ivana Kolingerová
Abstrakt CZ: Prezentovali jsme, jak se vyhnout nekonečným regionům u Voronoi diagramů 3D koulí. Nekonečné regiony jsou neohraničené reigony odpovídající koulím, jež jsou součástí konvexní obálky vstupní množiny. Tyto regiony mohou obsahovat Voronoi hrany jdoucí do nekonečna nebo vrcholy příliš vzdálené od konvexní obálky. Pokud se přímo nezajímáme o příliš vzdálené elementy diagramu, nebo pokud nechceme řešit problémy s nekonečnem, nabízí se použít nějaké hraniční omezení takového diagramu. Námi navržené omezení je založeno na přidání jediné inverzní koule do vstupní množiny. Pokud tato koule pojme celou vstupní množinu, zabrání kterékoliv hraně jít do nekonečna. Tento přístup aproximuje konvexní obálku vstupní množiny a lze jej s výhodou použít v algoritmech pro konstrukci těchto diagramů (např. edge-tracing).
Abstrakt EN: We show how to avoid infinite cells in Voronoi diagrams of 3D spheres. Infinite cells are unbounded cells at the convex-hull boundary of the input set. These cells can have Voronoi edges going to infinity or contain Voronoi vertices that are very distant from the convex hull. If our interest in parts of a diagram decreases as the distance from the convex hull increases or if we do not want to handle infinity, it might be useful to introduce a boundary constraint. We propose a constraint of extending the input set by a single inverted ball. When this ball encloses the entire input set, it stops any edge that would go to infinity otherwise. This approach only approximates the convex hull of the original input set. It is suitable for tracing-algorithms used for construction of these diagrams.
Klíčová slova

Zpět

Patička