Voronoi diagrams are useful for spatial reasoning among particles and there are many prior studies on their construction. However, most prior works were for the ordinary Voronoi diagrams of points in R2 and R3. Here we propose a robust algorithm for constructing the Voronoi diagram of spherical balls in R3, where the output is guaranteed to be at least topologically consistent. This topology-oriented incremental algorithm constructs the Voronoi diagram in O(n3) time in the worst case, whereas its empirical time behavior shows a strong linear fashion for all data we tested. The proposed algorithm is the three-dimensional generalization of its counterpart in the plane. It is implemented, thoroughly tested, and compared with two well-known programs. Current implementation processes approximately 350 balls per second using one core of ordinary desktop computer. This paper also contains an extensive review on the Voronoi diagrams of 2D circular disks and 3D spherical balls. We anticipate the algorithm will be widely used to solve application problems from many disciplines in science and engineering. The library is freely available from the github repository.

Abstract The minimal convex hulls of disks problem is to find such arrangements of circular disks in the plane that minimize the length of the convex hull boundary. The mixed-integer non-linear programming model, named [17], works only for small to moderate-sized problems. Here we propose a polylithic framework of the problem for big problem instances by combining the following algorithms and models: (i) A fast disk-packing algorithm based on Voronoi diagrams, non-linear programming (NLP) models for packing disks, and an NLP model for minimizing the discretized perimeter of convex hull; (ii) A fast convex-hull algorithm to compute the convex hulls of disk arrangements and their perimeter lengths; (iii) A mixed-integer NLP model taking the output of as its input. We present complete analytic solutions for small problems up to four disks and a semi-analytic mixed-integer linear programming model which yields exact solutions for strip packing problems with up to one thousand congruent disks. It turns out that the proposed polylithic approach works fine for large problem instances containing up to 1,000 disks. Monolithic and polylithic solutions using usually outperform other approaches. The polylithic approach yields better solutions than the results in [17] and provides a benchmark suite for further research.

Voronoi diagrams are powerful for understanding spatial properties. However, few reports have been made for moving generators despite their important applications. We present a topology-oriented event-increment (TOI-E) algorithm for constructing a Voronoi diagram of moving circular disks in the plane over the time horizon$[0, t^{\infty })$. The proposed TOI-E algorithm computes the event history of the Voronoi diagram over the entire time horizon in$O(k_F \log n + k_C n \log n)$time with$O(n \log n)$preprocessing time and$O(n + k_F + k_C)$memory for$n$disk generators,$k_F$edge flips, and$k_C$disk collisions during the time horizon. Given an event history, the Voronoi diagram of an arbitrary moment$t^{\ast}

The beta-complex is a construct derived from the Voronoi diagram of spherical balls of arbitrary radii and has proven a powerful capability for proximity reasoning among spherical balls in three-dimensional space. Important applications related to molecular shapes in structural/computational molecular biology have been correctly, efficiently, and conveniently solved in the unified framework of the beta-complex and the Voronoi diagram. The beta-complex is a generalization of the ordinary alpha-complex. However, there are similarities and dissimilarities between the two complexes and it is necessary to correctly understand these similarities and dissimilarities to choose the right complex to solve application problems at hand. This paper presents the similarities and dissimilarities between these constructs and illustrates the consequence of the dissimilarity in application problems from both theoretical and practical points of view using examples of atomic arrangements.

3D printing, also called additive manufacturing, has been increasingly popular and printing efficiency has become more critical. To print artifacts faster with less material, thus leading to lighter and cheaper printed products, various types of void structureshave been designed and engineered inside of shape models. In this paper, we present a novel method for generating support-free elliptic hollowing for 3D shapes which can entirely avoid additional supporting structures. To achieve this, we perform the ellipse hollowing in one of the cross sectional polygons and then extrude the hollowed ellipses to the other parallel cross sections. To efficiently pack the ellipses in the polygon, we construct the Voronoi diagram of ellipses to reason the free-space around the ellipses and other geometric features by taking advantage of the available algorithm for the efficient and robust construction of the Voronoi diagram of circles. We demonstrate the effectiveness and feasibility of our proposed method by designing and printing support-free hollow for various 3D shapes using Poretron, the program which computes the hollow by embedding appropriate APIs of the Voronoi Diagram Machine library that is freely available from Voronoi Diagram Research Center. It takes a 3D mesh model and produces an STL file which can be either fed into a 3D printer or postprocessed.

Voronoi diagrams are useful for spatial reasoning, and the robust and efficient construction of the ordinary Voronoi diagram of points is well known. However, its counterpart for circular disks in R 2 and spherical balls in R 3 remains a challenge. In this article, we propose a topology-oriented incremental algorithm which robustly and efficiently computes a Voronoi diagram by incrementing a new disk generator to an existing one. The key idea is to enforce the convexity of the Voronoi cell corresponding to the incrementing disk so that a simple variation of the algorithm for points proposed by Sugihara in 1992 can be applied. A benchmark using both random and degenerate disks shows that the proposed algorithm is superior to CGAL in both computational efficiency and algorithmic robustness.

The medial axis is an important shape representation that finds a wide range of applications in shape analysis. For large-scale shapes of high resolution, a progressive medial axis representation that starts with the lowest resolution and gradually adds more details is desired. In this paper, we propose a fast and robust geometric algorithm that computes progressive medial axes of a large-scale planar shape. The key ingredient of our method is a novel structural analysis of merging medial axes of two planar shapes along a shared boundary. Our method is robust by separating the analysis of topological structure from numerical computation. Our method is also fast and we show that the time complexity of merging two medial axes is$O(n\;\log n_v)$, where$n$is the number of total boundary generators,$n_v$is strictly smaller than$n$and behaves as a small constant in all our experiments. Experiments on large-scale polygonal data and comparison with state-of-the-art methods show the efficiency and effectiveness of the proposed method.

Geometric properties are critical for the function of molecules consisting of atoms which are usually modeled as a set of spheres in 3D. We propose "Molecular Geometry" which is a theoretical framework of computational understanding of the geometry of molecules in the claim that most, hopefully all, molecular structure problems can be effectively and efficiently facilitated by the "geometrization" of the problem at hand. We also report BULL!, the molecular geometry engine based on the Voronoi diagram of spheres, the quasi-triangulation, and the beta-complex. Being a program implemented in C++, application programmers can simply call API-functions of BULL! to create application programs correctly, efficiently, and conveniently. The BULL! engine, which will be freely available from the Voronoi Diagram Research Center at Hanyang University, is designed so that application programs are completely independent of future modifications and improvements.

Quasi-triangulation is the dual structure of the Voronoi diagram of spheres, and it has been used as a convenient and powerful geometric construct for representing the proximity among spherical particles with different radii. In this paper, we present the formalism of the quasi-triangulation based on a quasi-world model and define primitive query operators called quasi-operators for correct and efficient topology traversal on the quasi-triangulation. Algorithms for the quasi-operators are also presented based on the extended inter-world data structure. The proposed quasi-operators have the potential to be a fundamental platform on which efficient algorithms for application problems on quasi-triangulation can be correctly and easily developed. The recently announced powerful constructs of the β-complex and the β-shape are such examples.

The proximity and topology among particles are often the most important factor for understanding the spatial structure of particles. Reasoning the morphological structure of molecules and reconstructing a surface from a point set are examples where proximity among particles is important. Traditionally, the Voronoi diagram of points, the power diagram, the Delaunay triangulation, and the regular triangulation, etc. have been used for understanding proximity among particles. In this paper, we present the theory of the β-shape and the β-complex and the corresponding algorithms for reasoning proximity among a set of spherical particles, both using the quasi-triangulation which is the dual of the Voronoi diagram of spheres. Given the Voronoi diagram of spheres, we first transform the Voronoi diagram to the quasi-triangulation. Then, we compute some intervals called β-intervals for the singular, regular, and interior states of each simplex in the quasi-triangulation. From the sorted set of simplexes, the β-shape and the β-complex corresponding to a particular value of β can be found efficiently. Given the Voronoi diagram of spheres, the quasi-triangulation can be obtained in O(m) time in the worst case, where m represents the number of simplexes in the quasi-triangulation. Then, the β-intervals for all simplexes in the quasi-triangulation can also be computed in O(m) time in the worst case. After sorting the simplexes using the low bound values of the β-intervals of each simplex in O(mlogm) time, the β-shape and the β-complex can be computed in O(logm+k) time in the worst case by a binary search followed by a sequential search in the neighborhood, where k represents the number of simplexes in the β-shape or the β-complex. The presented theory of the β-shape and the β-complex will be equally useful for diverse areas such as structural biology, computer graphics, geometric modelling, computational geometry, CAD, physics, and chemistry, where the core hurdle lies in determining the proximity among spherical particles.

The concept of a β-shape has been recently proposed by extending the concept of the well-known α-shape. Since the β-shape takes full consideration of the Euclidean geometry of spherical particles, it is better suited than the (weighted) α-shape for applications using spatial queries on the system of variable sized spheres based on the Euclidean distance metric. In this paper, we present an efficient and elegant algorithm which computers a β-shape from a quasi-triangulation in O(log m + k) time in the worst case, where the quasi-triangulation has m simplicies and the boundary of β-shape consists of k simplicies. We believe that the β-shape and β-complex for a set of variable sized spheres (such as the atoms in a protein) will be very useful in the near future since the precise and efficient analysis of molecular structure can be conveniently facilitated by using these structures.

BACKGROUND: Most proteins function by interacting with other molecules. Their interaction interfaces are highly conserved throughout evolution to avoid undesirable interactions that lead to fatal disorders in cells. Rational drug discovery includes computational methods to identify the interaction sites of lead compounds to the target molecules. Identifying and classifying protein interaction interfaces on a large scale can help researchers discover drug targets more efficiently. DESCRIPTION: We introduce a large-scale protein domain interaction interface database called InterPare http://interpare.net. It contains both inter-chain (between chains) interfaces and intra-chain (within chain) interfaces. InterPare uses three methods to detect interfaces: 1) the geometric distance method for checking the distance between atoms that belong to different domains, 2) Accessible Surface Area (ASA), a method for detecting the buried region of a protein that is detached from a solvent when forming multimers or complexes, and 3) the Voronoi diagram, a computational geometry method that uses a mathematical definition of interface regions. InterPare includes visualization tools to display protein interior, surface, and interaction interfaces. It also provides statistics such as the amino acid propensities of queried protein according to its interior, surface, and interface region. The atom coordinates that belong to interface, surface, and interior regions can be downloaded from the website. CONCLUSION: InterPare is an open and public database server for protein interaction interface information. It contains the large-scale interface data for proteins whose 3D-structures are known. As of November 2004, there were 10,583 (Geometric distance), 10,431 (ASA), and 11,010 (Voronoi diagram) entries in the Protein Data Bank (PDB) containing interfaces, according to the above three methods. In the case of the geometric distance method, there are 31,620 inter-chain domain-domain interaction interfaces and 12,758 intra-chain domain-domain interfaces.

While the compression of topology and geometry has been explored significantly, the same issue for normals has not yet been studied as much as it deserves. Presented in this paper is a better approach than existing ones to compress the normals of a mesh model. The proposed scheme uses relative indexing to refer to the normals from each face definition. Besides, this scheme uses the concept of clustering of model normals so that the distribution of normals is considered.

The transmission of 3D shape models via the Internet has become one of the hottest issues these days. Presented in this paper is a new approach for the rapid transmission of the geometric data of a shape model. By analysing three important factors for the data compression (the shape fidelity, the file size and the decompression time), we point out the potential problems with the previous approach of using the deltas between consecutive vertices and we propose an alternative of directly using the position values of the vertices of the model. It turns out that the proposed approach has a smaller file size, it has less distortion in the model, and the decompression is faster.

Computation of the characteristic points such as inflection points or cusp on a curve is often necessary in CAGD applications. When a curve is represented in a B-spline form, such computations can be made easier once it is transformed in a set of polynomial curves in a power form. Once a curve is represented in a power form, a point evaluation can be also made faster due to Horner's rule even though some issues of stability remains. In addition, the implicitization process of a parametric curve using a resultant usually requires the geometry represented in a power form. Usual practice of the transformation of a B-spline curve into a set of piecewise polynomial curves in a power form is done by either a knot refinement followed by basis conversions, or applying a Taylor expansion on the B-spline curve for each knot span. Presented in this paper is a new algorithm, called direct expansion, for the problem. The algorithm first locates the coefficients of all the linear terms that make up the basis functions in a knot span, and then the algorithm directly obtains the power form representation of basis functions by expanding the summation of products of appropriate linear terms. Then, a polynomial segment of a knot span can be easily obtained by the summation of products of the basis functions within the knot span with corresponding control points. Repeating this operation for each knot span, all of the polynomials of the B-spline curve can be transformed into a power form.