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.

Triangulation is one of the fundamental problems in computational geometry and computer graphics community, and it has huge application areas such as 3D printing, computer-aided engineering, surface reconstruction, surface visualization, and so on. The Delaunay refinement algorithm is a well-known method to generate quality triangular meshes when point cloud and/or constrained edges are given in two- or three-dimensional space. In this paper, we propose a simple but efficient algorithm to triangulate Voronoi surfaces of Voronoi diagram of spheres in 3-dimensional Euclidean space. The proposed algorithm is based on the Ruppert’s Delaunay refinement algorithm, and we modified the algorithm to be applied to the triangulation of Voronoi surfaces in two ways. First, a new method to deciding the location of a newly added vertex on the surface in 3-dimensional space is proposed. Second, a new efficient but effective way of estimating approximation error between Voronoi surface and triangulation. Because the proposed algorithm generates a triangular mesh for Voronoi surfaces with guaranteed quality, users can control the level of quality of the resulting triangulation that their application problems require. We have implemented and tested the proposed algorithm for random non-intersecting spheres, and the experimental result shows the proposed algorithm produces quality triangulations on Voronoi surfaces satisfying the quality criterion.

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.

In this paper, we consider the problem of regrouping a number of service sites into a smaller number of service sites called centers. Each service site is represented as a point in the plane and has an associated value of service demand. We aim to group the sites so that each group has the balanced service demand and the sum of distances from the sites in the group to their corresponding center is minimized. To solve this problem, we propose a hybrid genetic algorithm that is combined with Voronoi diagrams. We provide a variety of experimental results by changing the weights of the two factors: service demands and distances. Our hybrid algorithm finds good approximate solutions in a shorter computation time in comparison with optimal solution by integer programming.

Given a protein, it is often necessary to study its geometric and physicochemical properties for studying its structure and predicting funtions of a protein. In this case, a connolly surface of a protein plays important roles for these purpose. A protein consists of a set of amino acids and a set of atoms comprise an amino acide. Since an atom can be represented by a hard 3D sphere in van der Waals model, a protein is usually modeled as a set of 3D spheres. In this paper, we present the algorithm for computing a connolly surface using Euclidean Voronoi diagram atoms of a protein. The algorithm initially locates the exterior aotms of a protein where connolly surface patches exist and computes the patches by tracking their boundary curves. Since a Euclidean Voronoi diagram is uniquely defined independent of probe radius different from other geometric structures, the connolly surfaces defined by probes of different radii can be computed without re-computing the Euclidean Voronoi 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.

Presented in this paper is an algorithm to compute the Voronoi diagram of a circle set from the Voronoi diagram of a point set. The circles are located in Euclidean plane, the radii of the circles are non-negative and not necessarily equal, and the circles are allowed to intersect each other. The idea of the algorithm is to use the topology of the point set Voronoi diagram as a seed so that the correct topology of the circle set Voronoi diagram can be obtained through a number of edge flipping operations. Then, the geometries of the Voronoi edges of the circle set Voronoi diagram are computed. The main advantages of the proposed algorithm are in its robustness, speed, and the simplicity in its concept as well as implementation.