2차원 평면에서 점들의 집합에 대한 보로노이 다이어그램을 구현하는 경우는 비사실적 렌더링이나 스타일화 된 렌더링에 매우 자주 사용하는 기법이다. 하지만 기존의 연구들의 구현 방법을 살펴보면 픽셀기반의 이미지 공간에서 보로노이 셀을 계산하는 방식이 활용된다. 벡터기반의 보로노이 다이어그램의 구현은 셀들이 만나서 이루는 경계부분을 직접적으로 표현할 수 있는 방식이다. 픽셀 기반의 방법의 경우 보로노이 셀간의 경계는 이미지 형태로 먼저 만든 후 에지 추출 영상 처리를 통해 얻을 수 있으며 해상도에 따라 정확도가 결정되며 벡터 기반의 방법보다 부정확할 수 밖에 없다. 즉, 픽셀 기반의 보로노이 다이어그램 생성 방법은 보로노이 셀 영역을 위주로 계산하게 되고 명확한 경계에 대한 데이터를 명시적으로 가지고 있지 않는다. 이와는 대조 적으로 벡터 기반의 보로노이 다이어그램 생성 방법은 보로노이 다이어그램의 경계선 데이터를 직접 포함하 고 있으므로 정확도가 높은 표현 방법이라고 할 수 있다. 다만 픽셀기반의 구현 방법이 좀 더 직관적이고 쉬 운 구현 방법이라는 점 때문에 기존의 연구들은 픽셀기반의 구현을 사용하고 있다. 본 연구에서는 점에 직접 폴리곤 지오메트리를 사용하여 3차원 공간에서 보로노이 다이어그램을 계산하는 방법을 제안한다. 유클리드 거리와 맨해튼 거리를 모두 사용할 수 있으며 선분에 대한 보로노이 다이어그램의 확장에도 사용할 수 있도 록 제안하였다.

This paper presents a numerically robust algorithm to construct a Voronoi diagram of circles in the plane. The circles are allowed to have intersections among them, but one circle cannot fully contain another circle. The Voronoi diagram is a tessellation of the plane into Voronoi regions of given circles. Each circle has its Voronoi region which is defined by a set of points in the plane closer to the circle than any other circles. The distance from a point p to a circle ci of center pi and radius ri is ||p-pi||-ri, which is the closest Euclidean distance from p to the circle boundary. The proposed algorithm first constructs the point Voronoi diagram of centers of given circles, then it enlarges each point to the circle and expands its Voronoi region accordingly. This region-expansion process is done by local modifications and after completing this process for the whole circles the desired circle Voronoi diagram can be obtained. The proposed algorithm is numerically robust and we provide with a few examples to show its robustness. The algorithm runs in O(n2) time in the worst case and O(n) time on average where n is the number of the circles. The experiment shows that the region-expansion algorithm is robust and runs fast with strong linear time behavior.

The Voronoi diagram of spheres and power diagram have been known as powerful tools to analyze spatial characteristics of weighted points, and these structures have variety range of applications including molecular spatial structure analysis, location based optimization, architectural design, etc. Due to the fact that both diagrams are based on different distance metrics, one has better usability than another depending on application problems. In this paper, we compare these diagrams in various situations from the user’s viewpoint, and show the Voronoi diagram of spheres is more effective in the problems based on the Euclidean distance metric such as nearest neighbor search, path bottleneck locating, and internal void finding.

Guarino Guarini(1624-1683) is one of great Baroque architects who developed new spatial concept in architecture. He refused to static space typically appeared in Renaissance architecture. Instead, to make it possible to generate complicate form and moving space, he made use of generative diagram. It provide him with an abstract machine to generate automatically architectural inferiority. His generative diagram consists of three types: single circle diagram, matrix diagram and longitudinal diagram. The first diagram uses single circle as primary generator and develop this by means of overlap and equiangular division. La Cappella della Santissima Sindone, Sanctuary of Chiesa di Oropa, Chiesa dei Padri Somaschi, San Gaetano are designed according to this diagram. The generator of the second diagram is nine circles in $3{\times}3$ matrix, which provide the base for the interpenetration of space in Guarini's architecture. He inspired this diagram from Kepler's $\ulcorner$Harmonices mundi$\lrcorner$. The Churches of San Lorenzo, Ste-Anne-la-Royale, San Filippo Neri, San Gaetano are generated by this diagram. The third diagram has several circles in Lantin-cross plan. Guarini adopted this diagram because he had chances to design several churches in Northern Europe. The churches of Santa Maria di Ettinga, Immacolata Concezione, San Maria della Divina Providenza, Church without Name, San Filippo Neri are representative examples for this diagram.

Euclidean Voronoi diagram of spheres in 3D has not been explored as much as it deserves even though it has significant potential impacts on diverse applications in both science and engineering. In addition, studies on the data structure for its topology have not been reported yet. Presented in this paper is the topological representation for Euclidean Voronoi diagram of spheres which is represented as a cell structure as one of typical non-manifold models. The topological representation is a variation of radial edge data structure with a consideration on the topological characteristics of Euclidean Voronoi diagram of spheres distinguished from general non-manifold models and Euclidean Voronoi diagram of points. Various topological queries in the Voronoi diagram are also presented and analyzed.

It is known that Voronoi diagrams have many important applications in science and engineering as a useful tool for analyzing spatial properties among geometric objects. In this paper, we propose an algorithm to construct Euclidean Voronoi diagram for spheres in 3-dimensional space. Starting from the ordinary Voronoi diagram of centers of spheres, the proposed region-expansion algorithm constructs the desired diagram by expanding Voronoi regions for one sphere after another via a series of topology operations. While the worst-case time complexity is O(n3 log n) for the whole diagram, its expected time complexity can be much smaller.

Presented in this paper is an algorithm to compute a Voronoi diagram of circles in a circle, where circles are located in a large circle. Given circles in a large circle, the region in the plane is divided into regions associated with the given circles. The proposed algorithm uses point Voronoi diagram, and then some topological remedies are applied so that we obtain proper initial topology including enclosing circle. From this initial topology, we can obtain the correct topology by a series of edge-flip operations. After getting the correct topology, the equations of edges are computed and represented in a rational quadratic Bézier curve form.