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.

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.

This paper presents a method for designing solid shapes containing slopes where orientation appears opposite to the actual orientation when observed from a unique vantage viewpoint. The resulting solids generate a new type of visual illusion, which we call “impossible motion”, in which balls placed on the slopes appear to roll uphill thereby defying the law of gravity. This is possible because a single retinal image lacks depth information and human visual perception tries to interpret images as the most familiar shape even though there are infinitely many possible interpretations. We specify the set of all possible solids represented by a single picture as the solution set of a system of equations and inequalities, and then relax the constraints in such a way that the antigravity slopes can be reconstructed. We present this design procedure with examples.

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.

To make geometric computation robust against numerical errors is one of the most important issues for practical applications of geometric algorithms. We first review existing approaches to robust geometric computation, and next show that there still remain many difficulties. Finally we discuss possible directions to overcome these difficulties and thus to achieve superrobustness.

The purpose of this research is to construct a surface (1) passing through all unorganized data points, (2) with G/sup 1/-continuity and (3) with the minimum square-sum of the principal curvatures K/sub 1//sup 2/+K/sub 2//sup 2/ over the surface. In order to construct surfaces with these three characteristics, we construct the triangular mesh spanning the data points, cover it with Bezier patches, achieve continuity between patches, and minimize the curvature to prevent the surfaces from having flat places and unnecessary undulations. The performance of the proposed method is evaluated by computational experiments.

We present an algorithm for computing Minkowski sums among surfaces of revolution and surfaces of linear extrusion, generated by slope-monotone closed curves. The special structure of these simple surfaces allows the process of normal matching between two surfaces to be expressed as an explicit equation. Based on this insight, we also present an efficient algorithm for computing the distance between two simple surfaces, even though they may in general be non-convex. Using an experimental implementation, the distance between two surfaces of revolution was computed in less than 0.5 msec on average.

Article Free Access Share on Voronoi-based interpolation with higher continuity Authors: Hisamoto Hiyoshi Department of Mathematical Engineering and Information Physics, University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-8656, Japan Department of Mathematical Engineering and Information Physics, University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-8656, JapanView Profile , Kokichi Sugihara Department of Mathematical Engineering and Information Physics, University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-8656, Japan Department of Mathematical Engineering and Information Physics, University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-8656, JapanView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 242–250https://doi.org/10.1145/336154.336210Published:01 May 2000Publication History 25citation935DownloadsMetricsTotal Citations25Total Downloads935Last 12 Months50Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper presents a general framework for constructing a variety of multi-dimensional interpolants based on Voronoi diagrams. This framework includes previously known methods such as Sibson's interpolant and Laplace's interpolant; moreover it contains infinitely many new interpolants. Computational experiments suggest that the smoothness can be improved by the proposed generalization. In addition, this framework also includes the piecewise linear interpolant over the Delaunay triangulation, which is a finite-element interpolant. This fact suggests that already established techniques in the finite element method might be brought into the research of the Voronoi-based approach. Hence this framework gives a new and promising direction of research on interpolation based on Voronoi diagrams.

An incremental algorithm for constructing the four-dimensional convex hull is implemented using exact arithmetic together with the symbolic perturbation technique. Exact judgement of the topological structure of the four-dimensional convex hull requires about four times higher precision than the input. To decrease this computational cost, the lazy evaluation scheme is used. Experiments show that the computation can be accelerated more than one hundred times for nondegenerate input and more than three times even for highly degenerate input.

Recently the authors found a local coordinate property based on the planar Voronoi diagram that is simpler than the famous Sibson's local coordinates (R. Sibson, 1980; 1981), and proposed an interpolant using this property. The paper generalizes this property to general dimensions. The proof given in the paper enables us to use more general Voronoi diagrams, e.g., Laguerre Voronoi diagrams and numerically distributed Voronoi diagrams obtained by topology oriented algorithms. The paper also generalizes the author's interpolant to continuously distributed data sites.

The paper presents a method for accelerating an exact arithmetic geometric algorithm. The exact arithmetic is one of the most promising approaches for making numerically robust geometric algorithms, because it enables us to always judge the topological structures of objects correctly and thus makes us free from inconsistency. However, exact arithmetic costs much more time than floating point arithmetic. In order to decrease this cost, the paper studies a hybrid method using both exact and floating point arithmetic. For each judgement in the algorithm, floating point arithmetic is first applied, and exact arithmetic is used only when the floating point computation is not reliable. This idea is applied to the construction of three dimensional convex hulls, and experiments show that 80/spl sim/95% of the computational cost can be saved.

Abstract This paper presents a numerically robust and topologically consistent algorithm for intersecting convex polyhedra. This algorithm is new in the sense that the consistency issue is completely separated from the numerical error issue. The intersection operation is combinatorially abstracted as the operation of changing the vertex‐edge graphs associated with the input polyhedra, and numerical computation is employed only for choosing the branch of processing which is most likely to lead to the correct solution of the problem. Hence, the resultant algorithm is completely free from topological inconsistency.

An ordinary geographical information system has a collection of nearest neighbourhood operations, such as generating a buffer zone and searching for the nearest facility from a given location, and this collection serves as a useful tool box for spatial analysis. Computationally, these operations are undertaken through the ordinary Voronoi diagram. This paper extends this tool box by generalizing the ordinary Voronoi diagram. The tool box consists of 35 nearest neighbourhood operations based upon twelve generalized Voronoi diagrams: the order-fe Voronoi diagram, the ordered order-fc Voronoi diagram, the farthest-point Voronoi diagram, the kth-nearest-point Voronoi diagram, the weighted Voronoi diagram, the line Voronoi diagram, the area Voronoi diagram, the Manhattan Voronoi diagram, the spherical Voronoi diagram, the Voronoi diagram in a river, the polyhedral Voronoi diagram, and the network Voronoi diagram. Each operation is illustrated with examples and the literature of computational methods.

A numerically stable algorithm for constructing Voronoi diagrams in the plane is presented. In this algorithm higher priority is placed on the topological structure than on numerical values, so that, however large the numerical errors, the algorithm will never come across topological inconsistency and thus can always complete its task. The behavior of the algorithm is shown with examples, including one for as many as 10/sup 6/ generators.>

As Shapira pointed out, a theorem by the author on line drawings of polyhedral scenes was not accurate. The present paper shows that the validity of the theorem is attained by a slight revision of the formulation.

Mathematical structures of line drawings of polyhedrons are studied and practical as well as theoretical solutions are obtained for several fundamental problems aroused in scene analysis and in man-machine communication. First, a necessary and sufficient condition for a line drawing to correctly represent a polyhedron is obtained in terms of linear algebra. Next, combinatorial structures are investigated and practical solutions are obtained to such problems as how to discriminate between correct and incorrect line drawings and how to correct vertex-position errors in incorrect line drawings. Lastly, distribution of the degree of freedom of a line drawing is elucidated and a method is proposed for interactive reconstruction of a polyhedron from a line drawing. The results obtained here enable us to make manmachine communication more ``flexible'' in the sense that a machine can reconstruct three-dimensional objects from hand-drawn pictures even if the pictures are not perfect.