Exploration of Empty Space among Spherical Obstacles via Additively Weighted Voronoi Diagram

dc.contributor.authorManak, Martinen_US
dc.contributor.editorMaks Ovsjanikov and Daniele Panozzoen_US
dc.date.accessioned2016-06-17T14:12:10Z
dc.date.available2016-06-17T14:12:10Z
dc.date.issued2016en_US
dc.description.abstractProperties of granular materials or molecular structures are often studied on a simple geometric model - a set of 3D balls. If the balls simultaneously change in size by a constant speed, topological properties of the empty space outside all these balls may also change. Capturing the changes and their subsequent classification may reveal useful information about the model. This has already been solved for balls of the same size, but only an approximate solution has been reported for balls of different sizes. These solutions work on simplicial complexes derived from the dual structure of the ordinary Voronoi diagram of ball centers and use the mathematical concept of simplicial homology groups. If the balls have different radii, it is more appropriate to use the additively weighted Voronoi diagram (also known as the Apollonius diagram) instead of the ordinary diagram, but the dual structure is no longer a simplicial complex, so the previous approaches cannot be used directly. In this paper, a method is proposed to overcome this problem. The method works with Voronoi edges and vertices instead of the dual structure. Additional bridge edges are introduced to overcome disconnected cases. The output is a tree graph of events where cavities are created or merged during a simulated shrinking of the balls. This graph is then reorganized and filtered according to some criteria to get a more concise information about the development of the empty space in the model.en_US
dc.description.number5en_US
dc.description.sectionheadersVoronoi et al.en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume35en_US
dc.identifier.doi10.1111/cgf.12980en_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages249-258en_US
dc.identifier.urihttps://doi.org/10.1111/cgf.12980en_US
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectI.3.5 [Computer Graphics]en_US
dc.subjectComputational Geometry and Object Modelingen_US
dc.subjectHierarchy and geometric transformationsen_US
dc.titleExploration of Empty Space among Spherical Obstacles via Additively Weighted Voronoi Diagramen_US
Files