79 0

Topology-oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagram of Disks and Balls

Title
Topology-oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagram of Disks and Balls
Author
Mokwon Lee
Alternative Author(s)
이목원
Advisor(s)
김덕수
Issue Date
2019. 8
Publisher
한양대학교
Degree
Doctor
Abstract
보로노이 다이어그램은 입자들 사이의 공간적 추론을 하는데 유용하며 그 계산을 위한 많은 연구가 발표되어 있지만 이전 연구의 대부분은 2 차원과 3 차원 점들의 보로노이 다이어그램에 대한 연구이다. 본 논문에서는 2 차원에서 원의 보로노이 다이어그램과 3 차원에서 구의 보로노이 다이어그램을 계산하는 강건한 알고리즘을 제시하고자 한다. 본 논문에서 제시하는 위상 기반 증가 (TOI) 알고리즘은 이미 계산된 중간 단계의 보로노이 다이어그램에 위상 정보에 우선 순위를 두어 새로운 원 또는 구를 추가하면서 보로노이 다이어그램을 계산한다. TOI 알고리즘은 평균적으로 O(n)의 시간 복잡도를 가지며, 최악의 경우 2 차원 원의 TOI 알고리즘은 O(n2), 3 차원 구의 TOI 알고리즘은 O(n3)의 시간 복잡도를 갖는다. TOI 알고리즘은 이미 구현되어 있고, 다른 알고리즘과의 비교를 통해 철저히 테스트되었다.
Voronoi diagrams are useful for spatial reasoning among particles and many studies were reported on their construction. However, most prior works were for the ordinary Voronoi diagram of points in the two- or three-dimensional space. In this thesis, we propose a robust algorithm for constructing the Voronoi diagram of circular disks and spherical balls in the two- and three-dimensional space, respectively. The proposed topology-oriented incremental (TOI) algorithm constructs the Voronoi diagram in O(n) on average and O(n^2) (for disks) and O(n^3) (for balls) by incrementing a generator to an already-constructed intermediate Voronoi diagram with a priority on the topology. The TOI-algorithm was implemented and thoroughly tested to benchmark against other algorithms.
URI
http://dcollection.hanyang.ac.kr/common/orgView/000000110917https://repository.hanyang.ac.kr/handle/20.500.11754/109758
Appears in Collections:
GRADUATE SCHOOL[S](대학원) > MECHANICAL ENGINEERING(기계공학과) > Theses (Ph.D.)
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE