Details
| Original language | English |
|---|---|
| Title of host publication | 2007 International Conference on Cyberworlds |
| Subtitle of host publication | (CW'07) |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 376-385 |
| Number of pages | 10 |
| ISBN (print) | 0769530052, 9780769530055 |
| Publication status | Published - 2007 |
| Event | 2007 International Conference on Cyberworlds, CW'07 - Hannover, Germany Duration: 24 Oct 2007 → 27 Oct 2007 |
Abstract
The Voronoi diagram has been investigated intensively throughout the last decades. This has been done not only in the context of Euclidean geometry but also in curved spaces. Except for [KWR97] these methods typically make use of some fast marching cube algorithms. In this work we will focus on the computation of Voronoi diagrams including Voronoi objects that are contained in a Riemannian manifold M. Further, we assume throughout this paper that M has a differentiable structure consisting of smooth parametrisation functions f i i ε I, This is the reason why the approach presented in this work differs from the aforementioned algorithms. More accurate algorithms can be obtained by using to some medial equations that heavily involve normal coordinates. This approach relies on the precise computation of shortest joins of any two given points , q ε M. For these computations we did not apply shooting methods or related methods. Instead, we used a new perturbation method that operates on a family of deformed manifolds Mt, assuming that M0 has constant sectional curvature. To reduce time and space complexity of the introduced algorithm we suggest to use a randomised incremental construction scheme (RICS). Our approach assumes that those points fulfil a general position requirement for computing the geodesic Voronoi diagram for a set of points. Finally results of some computed Voronoi diagrams will be presented.
ASJC Scopus subject areas
- Computer Science(all)
- Computer Networks and Communications
- Computer Science(all)
- Human-Computer Interaction
- Social Sciences(all)
- Communication
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
2007 International Conference on Cyberworlds : (CW'07). Institute of Electrical and Electronics Engineers Inc., 2007. p. 376-385 4390942.
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Computation of Geodesic Voronoi Diagrams in Riemannian 3-Space using Medial Equations
AU - Naß, Henning
AU - Wolter, F. E.
AU - Thielhelm, Hannes
AU - Doǧan, Cem
PY - 2007
Y1 - 2007
N2 - The Voronoi diagram has been investigated intensively throughout the last decades. This has been done not only in the context of Euclidean geometry but also in curved spaces. Except for [KWR97] these methods typically make use of some fast marching cube algorithms. In this work we will focus on the computation of Voronoi diagrams including Voronoi objects that are contained in a Riemannian manifold M. Further, we assume throughout this paper that M has a differentiable structure consisting of smooth parametrisation functions f i i ε I, This is the reason why the approach presented in this work differs from the aforementioned algorithms. More accurate algorithms can be obtained by using to some medial equations that heavily involve normal coordinates. This approach relies on the precise computation of shortest joins of any two given points , q ε M. For these computations we did not apply shooting methods or related methods. Instead, we used a new perturbation method that operates on a family of deformed manifolds Mt, assuming that M0 has constant sectional curvature. To reduce time and space complexity of the introduced algorithm we suggest to use a randomised incremental construction scheme (RICS). Our approach assumes that those points fulfil a general position requirement for computing the geodesic Voronoi diagram for a set of points. Finally results of some computed Voronoi diagrams will be presented.
AB - The Voronoi diagram has been investigated intensively throughout the last decades. This has been done not only in the context of Euclidean geometry but also in curved spaces. Except for [KWR97] these methods typically make use of some fast marching cube algorithms. In this work we will focus on the computation of Voronoi diagrams including Voronoi objects that are contained in a Riemannian manifold M. Further, we assume throughout this paper that M has a differentiable structure consisting of smooth parametrisation functions f i i ε I, This is the reason why the approach presented in this work differs from the aforementioned algorithms. More accurate algorithms can be obtained by using to some medial equations that heavily involve normal coordinates. This approach relies on the precise computation of shortest joins of any two given points , q ε M. For these computations we did not apply shooting methods or related methods. Instead, we used a new perturbation method that operates on a family of deformed manifolds Mt, assuming that M0 has constant sectional curvature. To reduce time and space complexity of the introduced algorithm we suggest to use a randomised incremental construction scheme (RICS). Our approach assumes that those points fulfil a general position requirement for computing the geodesic Voronoi diagram for a set of points. Finally results of some computed Voronoi diagrams will be presented.
UR - http://www.scopus.com/inward/record.url?scp=46449089413&partnerID=8YFLogxK
U2 - 10.1109/CW.2007.52
DO - 10.1109/CW.2007.52
M3 - Conference contribution
AN - SCOPUS:46449089413
SN - 0769530052
SN - 9780769530055
SP - 376
EP - 385
BT - 2007 International Conference on Cyberworlds
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2007 International Conference on Cyberworlds, CW'07
Y2 - 24 October 2007 through 27 October 2007
ER -