The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
In this talk, I first cover the applications of Voronoi Diagram and Delaunay Triangulation based on my personal experience. On the successful part, I will cover the history and development of the Jump-and-Walk algorithm, which is known as the first sublinear geometric algorithm nowadays and has been used in several famous software packages. On the bioinformatics applications, I will focus on three...
I will consider two outstanding problems in the theory of Delaunay and Voronoi tilings for lattices. There is a new classification problem that has arisen from a new structure theorem. Sergei Ryshkov proved that: The Minkowski sum of two Voronoi polytopes is a Voronoi polytope, if and only if the corresponding Delaunay tilings are commensurate. This result raises the question of classifying all Minkowski...
Given two points A and B in the plane, we are interested in separating them by two curves CA and CB such that CA is equidistant from A and CB, and CB is equidistant from B and CA. Such curves generalize the familiar notion of a bisector curve, and form the basis of a new kind of Voronoi diagram called a Zone diagram. These curves, which are referred to as distance trisector curves, have been studied...
Given a set of line segments in the plane, we define an angular Voronoi diagram as follows: a point belongs to a Voronoi region of a line segment if the visual angle of the line segment from the point is smallest among all line segments. The Voronoi diagram is interesting in itself and different from an ordinary Voronoi diagram for a point set. After introducing interesting properties, we present...
Given a set P of n points in the plane and a set S of non-crossing line segments whose endpoints are in P, let CDT(P, S) be the constrained Delaunay triangulation of P with respect to S. Given any two visible points p, q \in P, we show that there exists a path from p to q in CDT(P, S), denoted SPCDT(p, q), such that every edge in the path has length at most |pq| and the ratio |SP CDT(p, q)|/|pq| is...
This paper considers a problem of finding an optimal point within a polygon P in the sense that when we connect the point to every vertex of P by straight line then the worst aspect ratio among all resulting triangles is optimized. This problem has an important application to triangular mesh improvement. We propose three different approaches toward this problem. The first one is based on some new...
The paper presents a simple method for extracting global medial axes in a stable manner. A new index, called the normalized boundary distance, is introduced in order to measure the degree of importance of a point on the conventional medial axis. This index has a remarkable property that the set of points whose index values are greater than an arbitrarily chosen threshold is topologically equivalent...
For one-qubit pure quantum states, it is already proved that the Voronoi diagrams with respect to two distances - Euclidean distance and the quantum divergence - coincide. This fact is a support for a known method to calculate the Holevo capacity. To consider an applicability of this method to quantum states of a higher level system, it is essential to check if the coincidence of the Voronoi diagrams...
We address the problemof robust point-locationin a generalized -dimensional Voronoi diagram. The exact point location requires the solution for expressions of degree four. A natural question is what can be done using expression of smaller degree. We apply polyhedral metrics for this task. In general dimensions two Minkowski metrics can be used L_1(Manhattan metric) and l_r00. The approximation factor...
The Delaunay diagram in d dimensions is the dual of the Voronoi diagram of a set of input sites. If we assume no degeneracies in the input, i.e. no d + 2 sites are co-spherical, then the diagram is a triangulation. Because this assumption is common, and can be enforced by symbolic perturbation, we often forget that Delaunay diagrams need not be triangulations. Input sets chosen from integer grids...
We propose a random field regarded as a generalization of Voronoi diagrams for the case where the positions of generators are distributed probabilistically. Our approach is a kind of stochastic approaches to Voronoi diagrams; however our definition is different from usual random Voronoi diagrams such as Poisson Voronoi diagrams. As numerical examples, first we discuss the case where the positions...
We describe two reversible line-drawing methods for cartographic applications based on the kinetic (moving-point) Voronoi diagram. Our objectives were to optimize the user?s ability to draw and edit the map, rather than to produce the most efficient batchoriented algorithm for large data sets, and all our algorithms are based on local operations (except for basic point location). Because the deletion...
The paper presents a unique utilization of the Dynamic Delaunay Triangulation (DT) to devise a highly efficient algorithm for the neighborhood adjacency management which is a crucial component of a swarm-based simulation. This algorithm allows fast computation of the swarm neighborhood which is required to implement Boids flocking rules. The method also provides an efficient mechanism to detect and...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.