Voronoi drawings of trees

We study the problem of characterizing sets of points whose Voronoi diagrams are trees and if so, what are the combinatorial properties of these trees. The second part of the problem can be naturally turned into the following graph drawing question: Given a tree T, can one represent T so that the resulting drawing is a Voronoi diagram of some set of points? We investigate the problem both in the Euclidean and in the Manhattan metric. The major contributions of this paper are as follows.

• We characterize those trees that can be drawn as Voronoi diagrams in the Euclidean metric.

• We characterize those sets of points whose Voronoi diagrams are trees in the Manhattan metric.

• We show that the maximum vertex degree of any tree that can be drawn as a Manhattan Voronoi diagram is at most five and prove that this bound is tight.

• We characterize those binary trees that can be drawn as Manhattan Voronoi diagrams.

Randomized incremental construction of simple abstract Voronoi diagrams in 3-space

We introduce the simple abstract Voronoi diagram in 3-space as an abstraction of the usual Voronoi diagram. We show that the 3-dimensional simple abstract Voronoi diagram of n sites can be computed in O(n²) expected time using O(n²) expected space by a randomized algorithm. The algorithm is based on the randomized incremental construction technique of Clarkson and Shor (1989). We apply the algorithm to some concrete types of such diagrams: power diagrams, diagrams under ellipsoid convex distance functions, and diagrams under the Hausdorff distance for sites that are parallel segments all having the same length.     

A nearest neighbor sweep circle algorithm for computing discrete Voronoi tessellations

An algorithm for computing discrete, 2-dimensional, Euclidean Voronoi tessellations is presented. The algorithm combines a limiting sweep circle approach with a nearest neighbor cellular approach. It reduces the computational cost of the naïve approach while at the same time giving the Euclidean Voronoi tessellations that simple nearest neighbor algorithms are unable to produce. The algorithm is shown, through analytical methods, to produce good approximations to corresponding continuous Voronoi tessellations depending on the definition of neighbor used in the nearest neighbor step and the mesh size. The quality of different types of neighbor definitions are discussed as well as the computational cost. The algorithm is general enough to be easily extended to higher dimensions and nonuniform meshes. The analysis lays the groundwork for the computation of discrete centroidal Voronoi tessellations where some kind of numerical integration is required.     

Farthest-polygon Voronoi diagrams

Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(nlog³n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k−1 connected components, but if one component is bounded, then it is equal to the entire region.     

On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes

It is well known that the complexity, i.e. the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n²). It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensional region such as a cube or sphere, then the expected complexity falls to O(n). In this paper we introduce the problem of analyzing what occurs if the points are chosen from a 2-dimensional region in 3-dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution with rate n on the surface of a convex polytope. We prove that, in this case, the expected complexity of the resulting Voronoi diagram is O(n).     

Computing generalized higher-order Voronoi diagrams on triangulated surfaces

We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.     

A Fast Robust Algorithm for Computing Discrete Voronoi Diagrams

We describe an algorithm for the construction of discretized Voronoi diagrams on a CPU within the context of a large scale numerical fluid simulation. The Discrete Voronoi Chain (DVC) algorithm is fast, flexible and robust. The algorithm stores the Voronoi diagram on a grid or lattice that may be structured or unstructured. The Voronoi diagram is computed by alternatively updating two lists of grid cells per particle to propagate a growth boundary of cells from the particle locations. Distance tests only occur when growth boundaries from different particles collide with each other, hence the number of distance tests is effectively minimized. We give some empirical results for two and three dimensions. The method generalizes to any dimension in a straight forward manner. The distance tests can be based any metric.     

Circular permutation graph family with applications

In a circular permutation diagram, there are two sets of terminals on two concentric circles: C_in and C_out. Given a permutation Π = [π₁, π₂, …, π_n], terminal i on C_in and terminal π_i on C_out are connected by a wire. The intersection graph G_c of a circular permutation diagram D_c is called a circular permutation graph of a permutation Π corresponding to the diagram D_c. The set of all circular permutation graphs of a permutation Π is called the circular permutation graph family of permutation Π. In this paper, we propose the following: (1) an O(V + E) time algorithm to check if a labeled graph G = (V, E) is a labeled circular permutation graph. (2) An O(n log n + nt) time algorithm to find a maximum independent set of a family, where n = Π and t is the cardinality of the output. (Number t in the worst case is O(n). However, if Π is uniformly distributed (and independent from i), its expected value is O(√n).) (3) An O(min(δV_clog logV_c,V_clogV_c) + E_c) time algorithm for finding a maximum independent set of a circular permutation diagram D_c, where δ is the minimum degree of vertices in the intersection graph G_c = (V_c,E_c) of D_c. (4) An O(n log log n) time algorithm for finding a maximum clique and the chromatic number of a circular permutation diagram, where n is the number of wires in the diagram.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

2D Centroidal Voronoi Tessellations with Constraints

<正>We tackle the problem of constructing 2D centroidal Voronoi tessellations with constraints through an efficient and robust construction of bounded Voronoi diagrams, the pseudo-dual of the constrained Delaunay triangulation.We exploit the fact that the cells of the bounded Voronoi diagram can be obtained by clipping the ordinary ones against the constrained Delaunay edges.The clipping itself is efficiently computed by identifying for each constrained edge the(connected) set of triangles whose dual Voronoi vertices are hidden by the constraint.The resulting construction is amenable to Lloyd relaxation so as to obtain a centroidal tessellation with constraints.     

The power crust, unions of balls, and the medial axis transform

The medial axis transform (or MAT) is a representation of an object as an infinite union of balls. We consider approximating the MAT of a three-dimensional object, and its complement, with a finite union of balls. Using this approximate MAT we define a new piecewise-linear approximation to the object surface, which we call the power crust.

We assume that we are given as input a sufficiently dense sample of points from the object surface. We select a subset of the Voronoi balls of the sample, the polar balls, as the union of balls representation. We bound the geometric error of the union, and of the corresponding power crust, and show that both representations are topologically correct as well. Thus, our results provide a new algorithm for surface reconstruction from sample points. By construction, the power crust is always the boundary of a polyhedral solid, so we avoid the polygonization, hole-filling or manifold extraction steps used in previous algorithms.

The union of balls representation and the power crust have corresponding piecewise-linear dual representations, which in some sense approximate the medial axis. We show a geometric relationship between these duals and the medial axis by proving that, as the sampling density goes to infinity, the set of poles, the centers of the polar balls, converges to the medial axis.     

A doubly cyclic channel assignment problem

A standard model for radio channel assignment involves a set V of sites, the set {0,1,2,…} of channels, and a constraint matrix (w(u, v)) specifying minimum channel separations. An assignment f:V→{0,1,2,…} is feasible if the distance f(u) − f(v)w(u, v) for each pair of sites u and v. The aim is to find the least k such that there is a feasible assignment using only the k channels 0, 1, …, k − 1, and to find a corresponding optimal assignment.

We consider here a related problem involving also two cycles. There is a given cyclic order τ on the sites, and feasible assignments f must also satisfy f(τv) f(v) for all except one site v. Further, the channels are taken to be evenly spaced around a circle, so that if the k channels 0, 1, …, k − 1 are available then the distance between channels i and j is the minimum of ¦i − j¦ and k − ¦i − j¦. We show how to find a corresponding optimal channel assignment in O(¦V¦³) steps.     

Stable marker-particle method for the Voronoi diagram in a flow field

The Voronoi diagram in a flow field is a tessellation of water surface into regions according to the nearest island in the sense of a “boat-sail distance”, which is a mathematical model of the shortest time for a boat to move from one point to another against the flow of water. The computation of the diagram is not easy, because the equi-distance curves have singularities. To overcome the difficulty, this paper derives a new system of equations that describes the motion of a particle along the shortest path starting at a given point on the boundary of an island, and thus gives a new variant of the marker-particle method. In the proposed method, each particle can be traced independently, and hence the computation can be done stably even though the equi-distance curves have singular points.     

The distance trisector curve

Given points p and q in the plane, we are interested in separating them by two curves C₁ and C₂ such that every point of C₁ has equal distance to p and to C₂, and every point of C₂ has equal distance to C₁ and to q. We show by elementary geometric means that such C₁ and C₂ exist and are unique. Moreover, for p=(0,1) and q=(0,−1), C₁ is the graph of a function , C₂ is the graph of −f, and f is convex and analytic (i.e., given by a convergent power series at a neighborhood of every point). We conjecture that f is not expressible by elementary functions and, in particular, not algebraic. We provide an algorithm that, given x∈R and ε>0, computes an approximation to f(x) with error at most ε in time polynomial in . The separation of two points by two “trisector” curves considered here is a special (two-point) case of a new kind of Voronoi diagram, which we call the zone diagram and which we investigate in a companion paper.     

Harary's conjectures on integral sum graphs

Let N denote the set of positive integers and Z denote all integers. The (integral) sum graph of a finite subset S N(Z) is the graph (S, E) with uv ε E if and only if u + v ε S. A graph G is said to be an (integral) sum graph if it is isomorphic to the (integral) sum graph of some S N(Z). The (integral) sum number of a given graph G is the smallest number of isolated nodes which when added to G result in an (integral) sum graph.

We show that the integral sum number of a complete graph with n 4 nodes equals 2n − 3, which proves a conjecture of Harary. And we disprove another conjecture of Harary by showing that there are infinitely many trees which are not caterpillars but are integral sum graphs.     

Maximin location: Discretization not always works

In this note we show by means of a simple example that, if the maximin problem with (nonlinear) concave increasing utility functions is solved by inspecting the extreme points of the (generalized) Voronoi diagram (as usually proposed), one may have to inspect an infinite number of candidate points. The research of the second and third authors is partially supported by Grant PB96-1416-C02-02 of Ministerio de Educación y Cultura, Spain     

Choosability conjectures and multicircuits

This paper starts with a discussion of several old and new conjectures about choosability in graphs. In particular, the list-colouring conjecture, that ch′=χ′ for every multigraph, is shown to imply that if a line graph is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t. It is proved that ch(H²)=χ(H²) for many “small” graphs H, including inflations of all circuits (connected 2-regular graphs) with length at most 11 except possibly length 9; and that ch″(C)=χ″(C) (the total chromatic number) for various multicircuits C, mainly of even order, where a multicircuit is a multigraph whose underlying simple graph is a circuit. In consequence, it is shown that if any of the corresponding graphs H² or T(C) is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t.     

On application of the Lanczos method to solution of some partial differential equations

Let A be a square symmetric n × n matrix, φ be a vector from ⁿ, and f be a function defined on the spectral interval of A. The problem of computation of the vector u = f(A)φ arises very often in mathematical physics.

We propose the following method to compute u. First, perform m steps of the Lanczos method with A and φ. Define the spectral Lanczos decomposition method (SLDM) solution as u_m = φ Qf(H)e₁, where Q is the n × m matrix of the m Lanczos vectors and H is the m × m tridiagonal symmetric matrix of the Lanczos method. We obtain estimates for u − u_m that are stable in the presence of computer round-off errors when using the simple Lanczos method.

We concentrate on computation of exp(− tA)φ, when A is nonnegative definite. Error estimates for this special case show superconvergence of the SLDM solution. Sample computational results are given for the two-dimensional equation of heat conduction. These results show that computational costs are reduced by a factor between 3 and 90 compared to the most efficient explicit time-stepping schemes. Finally, we consider application of SLDM to hyperbolic and elliptic equations.     

Solving the continuous space p-centre problem: planning application issues

^** Email: wei.97{at}osu.edu^*** Email: murray.308{at}osu.edu^**** Email: xiao.37{at}osu.edu The Voronoi diagram heuristic has been proposed for solvingthe p-centre problem in continuous space. However, importantassumptions underlie this heuristic and may be problematic forpractical applications. These simplifying assumptions includeuniformly distributed demand, representing a region as a rectangle;analysis of a simple Voronoi polygon in solving associated one-centreproblems and no restrictions on potential facility locations.In this paper, we explore the complexity of solving the continuousspace p-centre problem in location planning. Considering theissue of solution space feasibility, we present a spatiallyrestricted version of this problem and propose methods for solvingit heuristically. Theoretical and empirical results are provided.     

最小最大二点集覆盖问题分析及改进算法设计

本文考虑二中心问题的扩展问题-最小最大二点集覆盖问题。给定两个平面点集P₁和P₂,分别包含m和n个点,求两个圆分别覆盖P₁和P₂,并且要求两圆半径与两圆圆心距三者中的最大值最小。本文主要贡献在于分析半径变化过程中两个点集中心包之间最近距离的变化关系,其中中心包是点集所具有的一个特殊几何结构,所得到的结果改进了Huang等人之前给出的结果,并且通过该结果设计相应算法,所得到的算法复杂性是目前最好的。