GBGVD: Growth-based geodesic Voronoi diagrams
Given a set of generators, the geodesic Voronoi diagram (GVD) defines how the base surface is decomposed into separate regions such that each generator dominates a region in terms of geodesic distance to the generators. Generally speaking, each ordinary bisector point of the GVD is determined by two...
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2023-10-01
|
| Series: | Graphical Models |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1524070323000267 |
| _version_ | 1827805426050138112 |
|---|---|
| author | Yunjia Qi Chen Zong Yunxiao Zhang Shuangmin Chen Minfeng Xu Lingqiang Ran Jian Xu Shiqing Xin Ying He |
| author_facet | Yunjia Qi Chen Zong Yunxiao Zhang Shuangmin Chen Minfeng Xu Lingqiang Ran Jian Xu Shiqing Xin Ying He |
| author_sort | Yunjia Qi |
| collection | DOAJ |
| description | Given a set of generators, the geodesic Voronoi diagram (GVD) defines how the base surface is decomposed into separate regions such that each generator dominates a region in terms of geodesic distance to the generators. Generally speaking, each ordinary bisector point of the GVD is determined by two adjacent generators while each branching point of the GVD is given by at least three generators. When there are sufficiently many generators, straight-line distance serves as an effective alternative of geodesic distance for computing GVDs. However, for a set of sparse generators, one has to use exact or approximate geodesic distance instead, which requires a high computational cost to trace the bisectors and the branching points. We observe that it is easier to infer the branching points by stretching the ordinary segments than competing between wavefronts from different directions. Based on the observation, we develop an unfolding technique to compute the ordinary points of the GVD, as well as a growth-based technique to stretch the traced bisector segments such that they finally grow into a complete GVD. Experimental results show that our algorithm runs 3 times as fast as the state-of-the-art method at the same accuracy level. |
| first_indexed | 2024-03-11T21:25:22Z |
| format | Article |
| id | doaj.art-e97eb522d97b41a2937fffc1f85b6abd |
| institution | Directory Open Access Journal |
| issn | 1524-0703 |
| language | English |
| last_indexed | 2024-03-11T21:25:22Z |
| publishDate | 2023-10-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Graphical Models |
| spelling | doaj.art-e97eb522d97b41a2937fffc1f85b6abd2023-09-28T05:25:08ZengElsevierGraphical Models1524-07032023-10-01129101196GBGVD: Growth-based geodesic Voronoi diagramsYunjia Qi0Chen Zong1Yunxiao Zhang2Shuangmin Chen3Minfeng Xu4Lingqiang Ran5Jian Xu6Shiqing Xin7Ying He8Shandong University, Qingdao, ChinaShandong University, Qingdao, ChinaShandong University, Qingdao, ChinaQingdao University of Science and Technology, Qingdao, China; Corresponding author.Shandong University of Finance and Economics, Jinan, ChinaShandong University of Finance and Economics, Jinan, ChinaDalian University of Technology, Dalian, ChinaShandong University, Qingdao, ChinaNanyang Technological University, SingaporeGiven a set of generators, the geodesic Voronoi diagram (GVD) defines how the base surface is decomposed into separate regions such that each generator dominates a region in terms of geodesic distance to the generators. Generally speaking, each ordinary bisector point of the GVD is determined by two adjacent generators while each branching point of the GVD is given by at least three generators. When there are sufficiently many generators, straight-line distance serves as an effective alternative of geodesic distance for computing GVDs. However, for a set of sparse generators, one has to use exact or approximate geodesic distance instead, which requires a high computational cost to trace the bisectors and the branching points. We observe that it is easier to infer the branching points by stretching the ordinary segments than competing between wavefronts from different directions. Based on the observation, we develop an unfolding technique to compute the ordinary points of the GVD, as well as a growth-based technique to stretch the traced bisector segments such that they finally grow into a complete GVD. Experimental results show that our algorithm runs 3 times as fast as the state-of-the-art method at the same accuracy level.http://www.sciencedirect.com/science/article/pii/S1524070323000267Voronoi diagramGeodesic distancesFast marching methodTriangle meshComputational geometry |
| spellingShingle | Yunjia Qi Chen Zong Yunxiao Zhang Shuangmin Chen Minfeng Xu Lingqiang Ran Jian Xu Shiqing Xin Ying He GBGVD: Growth-based geodesic Voronoi diagrams Graphical Models Voronoi diagram Geodesic distances Fast marching method Triangle mesh Computational geometry |
| title | GBGVD: Growth-based geodesic Voronoi diagrams |
| title_full | GBGVD: Growth-based geodesic Voronoi diagrams |
| title_fullStr | GBGVD: Growth-based geodesic Voronoi diagrams |
| title_full_unstemmed | GBGVD: Growth-based geodesic Voronoi diagrams |
| title_short | GBGVD: Growth-based geodesic Voronoi diagrams |
| title_sort | gbgvd growth based geodesic voronoi diagrams |
| topic | Voronoi diagram Geodesic distances Fast marching method Triangle mesh Computational geometry |
| url | http://www.sciencedirect.com/science/article/pii/S1524070323000267 |
| work_keys_str_mv | AT yunjiaqi gbgvdgrowthbasedgeodesicvoronoidiagrams AT chenzong gbgvdgrowthbasedgeodesicvoronoidiagrams AT yunxiaozhang gbgvdgrowthbasedgeodesicvoronoidiagrams AT shuangminchen gbgvdgrowthbasedgeodesicvoronoidiagrams AT minfengxu gbgvdgrowthbasedgeodesicvoronoidiagrams AT lingqiangran gbgvdgrowthbasedgeodesicvoronoidiagrams AT jianxu gbgvdgrowthbasedgeodesicvoronoidiagrams AT shiqingxin gbgvdgrowthbasedgeodesicvoronoidiagrams AT yinghe gbgvdgrowthbasedgeodesicvoronoidiagrams |