Restricting Voronoi Diagrams to Meshes Using Corner Validation

Simple item page
dc.contributor.authorSainlot, Maximeen_US
dc.contributor.authorNivoliers, Vincenten_US
dc.contributor.authorAttali, Dominiqueen_US
dc.contributor.editorBærentzen, Jakob Andreas and Hildebrandt, Klausen_US
dc.date.accessioned2017-07-02T17:37:47Z
dc.date.available2017-07-02T17:37:47Z
dc.date.issued2017
dc.description.abstractRestricted Voronoi diagrams are a fundamental geometric structure used in many applications such as surface reconstruction from point sets or optimal transport. Given a set of sites V and a mesh X with vertices in Rd connected by triangles, the restricted Voronoi diagram partitions X by computing for each site the portion of X for which the site is the nearest. The restricted Voronoi diagram is the intersection between the regular Voronoi diagram and the mesh. Depending on the site distribution or the ambient space dimension computing the regular Voronoi diagram may not be feasible using classical algorithms. In this paper, we extend Lévy and Bonneel's approach [LB12] based on nearest neighbor queries. We show that their method is limited when the sites are not located on X. We propose a new algorithm for computing restricted Voronoi which reduces the number of sites considered for each triangle of the mesh and scales smoothly when the sites are far from the surface.en_US
dc.description.number5
dc.description.sectionheadersMeshing
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume36
dc.identifier.doi10.1111/cgf.13247
dc.identifier.issn1467-8659
dc.identifier.pages081-091
dc.identifier.urihttps://doi.org/10.1111/cgf.13247
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13247
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectI.3.3 [Computer Graphics]
dc.subjectPicture/Image Generation
dc.subjectLine and curve generation
dc.titleRestricting Voronoi Diagrams to Meshes Using Corner Validationen_US
Files
Collections
36-Issue 5