Přejít k obsahu


Fast Discovery of Voronoi Vertices in the Construction of Voronoi Diagram of 3D Balls

Citace: [] MAŇÁK, M., KOLINGEROVÁ, I. Fast Discovery of Voronoi Vertices in the Construction of Voronoi Diagram of 3D Balls. In Voronoi Diagrams in Science and Engineering. Los Alamitos: IEEE, 2010. s. 95-104. ISBN: 978-0-7695-4112-9
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Fast Discovery of Voronoi Vertices in the Construction of Voronoi Diagram of 3D Balls
Rok vydání: 2010
Místo konání: Los Alamitos
Název zdroje: IEEE
Autoři: Mgr. Martin Maňák , Prof. Dr. Ing. Ivana Kolingerová
Abstrakt CZ: Řešení geometrických problémů na množině koulí je výzvou na poli výpočetní geometrie. Tyto problémy lze efektivně řešit, pokud je k dispozici aditivně vážený Voronoi diagram pro tuto množinu. Diagram lze zkonstruovat pomocí algoritmu trasování hrany nebo podobných postupů, kdy se hledají vrcholy Voronoi diagramu podél hran. Avšak kvadratická časová složitost tohoto algoritmu jej činí nepraktickým. Algoritmus lze výrazně urychlit pomocí našeho nového postupu. Kdykoliv se hledá vrchol diagramu, prohledává se Delaunay triangulace středů koulí. Prohledávání se drží uvnitř prostorového filtru, který se může v průběhu prohledávání zmenšovat. Zlepšení očekávané časové složitosti je demonstrování na proteinových datech (množina koulí reprezentuje atomy v molekule), protože to je naše cílová aplikační doména.
Abstrakt EN: Solving geometrical problems on a set of 3D balls is a challenging task in computational geometry. They can be solved effectively when the Voronoi diagram for the set is available. The diagram is usually constructed by the edge-tracing or similar algorithms based on finding Voronoi vertices along edges. However, its expected quadratic time complexity makes it impractical. This can be improved significantly by our new approach. Whenever a vertex needs to be found, Delaunay triangulation of ball centers is searched through to find one specific ball. The search is kept inside a spatial filter, which can be reduced in size during the search. The improvement is demonstrated on protein data (a set of balls represents atoms in a molecule), because this is our intended application.
Klíčová slova

Zpět

Patička