Generalized Voronoi Diagrams and Lie Sphere Geometry
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914915343663104 |
|---|---|
| author | Edwards, John Payne, Tracy Schafer, Elena |
| author_facet | Edwards, John Payne, Tracy Schafer, Elena |
| contents | We use Lie sphere geometry to describe two large categories of generalized Voronoi diagrams that can be encoded in terms of the Lie quadric, the Lie inner product, and polyhedra. The first class consists of diagrams defined in terms of extremal spheres in the space of Lie spheres, and the second class includes minimization diagrams for functions that can be expressed in terms of affine functions on a higher-dimensional space. These results unify and generalize previous descriptions of generalized Voronoi diagrams as convex hull problems. Special cases include classical Voronoi diagrams, power diagrams, order $k$ and farthest point diagrams, Apollonius diagrams, medial axes, and generalized Voronoi diagrams whose sites are combinations of points, spheres and half-spaces. We describe the application of these results to algorithms for computing generalized Voronoi diagrams and find the complexity of these algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09279 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generalized Voronoi Diagrams and Lie Sphere Geometry Edwards, John Payne, Tracy Schafer, Elena Metric Geometry 51F99 I.3.5 We use Lie sphere geometry to describe two large categories of generalized Voronoi diagrams that can be encoded in terms of the Lie quadric, the Lie inner product, and polyhedra. The first class consists of diagrams defined in terms of extremal spheres in the space of Lie spheres, and the second class includes minimization diagrams for functions that can be expressed in terms of affine functions on a higher-dimensional space. These results unify and generalize previous descriptions of generalized Voronoi diagrams as convex hull problems. Special cases include classical Voronoi diagrams, power diagrams, order $k$ and farthest point diagrams, Apollonius diagrams, medial axes, and generalized Voronoi diagrams whose sites are combinations of points, spheres and half-spaces. We describe the application of these results to algorithms for computing generalized Voronoi diagrams and find the complexity of these algorithms. |
| title | Generalized Voronoi Diagrams and Lie Sphere Geometry |
| topic | Metric Geometry 51F99 I.3.5 |
| url | https://arxiv.org/abs/2408.09279 |