Constructing L∞ Voronoi diagrams in 2D and 3D

Simple item page
dc.contributor.authorBukenberger, D. R.
dc.contributor.authorBuchin, K.
dc.contributor.authorBotsch, M.
dc.date.accessioned2024-01-22T14:43:41Z
dc.date.available2024-01-22T14:43:41Z
dc.date.issued2022-10-06
dc.description.abstractVoronoi diagrams and their computation are well known in the Euclidean L2 space. They are easy to sample and render in generalized Lp spaces but nontrivial to construct geometrically. Especially the limit of this norm with p → ∞ lends itself to many quad- and hex-meshing related applications as the level-set in this space is a hypercube. Many application scenarios circumvent the actual computation of L∞ diagrams altogether as known concepts for these diagrams are limited to 2D, uniformly weighted and axis-aligned sites. Our novel algorithm allows for the construction of generalized L∞ Voronoi diagrams. Although parts of the developed concept theoretically extend to higher dimensions it is herein presented and evaluated for the 2D and 3D case. It further supports individually oriented sites and allows for generating weighted diagrams with anisotropic weight vectors for individual sites. The algorithm is designed around individual sites, and initializes their cells with a simple meshed representation of a site's level-set. Hyperplanes between adjacent cells cut the initialization geometry into convex polyhedra. Non-cell geometry is filtered out based on the L∞ Voronoi criterion, leaving only the non-convex cell geometry. Eventually we conclude with discussions on the algorithms complexity, numerical precision and analyze the applicability of our generalized L∞ diagrams for the construction of Centroidal Voronoi Tessellations (CVT) using Lloyd's algorithm.en
dc.identifier.urihttp://hdl.handle.net/2003/42291
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-24127
dc.language.isoende
dc.relation.ispartofseriesComputer graphics forum;41(5)
dc.rights.urihttps://creativecommons.org/licenses/by-nc/4.0/de
dc.subjectComputing methodologies → Mesh geometry modelsen
dc.subjectMesh modelsen
dc.subjectVolumetric modelsen
dc.subject.ddc004
dc.titleConstructing L∞ Voronoi diagrams in 2D and 3Den
dc.typeTextde
dc.type.publicationtypeArticlede
dcterms.accessRightsopen access
eldorado.secondarypublicationtruede
eldorado.secondarypublication.primarycitationBukenberger, D.R., Buchin, K. and Botsch, M. (2022), Constructing L∞ Voronoi Diagrams in 2D and 3D. Computer Graphics Forum, 41: 135-147. https://doi.org/10.1111/cgf.14609de
eldorado.secondarypublication.primaryidentifierhttps://doi.org/10.1111/cgf.14609de

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Computer Graphics Forum - 2022 - Bukenberger - Constructing L Voronoi Diagrams in 2D and 3D.pdf
Size:
11.32 MB
Format:
Adobe Portable Document Format
Description:
DNB
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.85 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

LS 07 Graphische Systeme