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.     

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.     

Re-examination of Bregman functions and new properties of their divergences

ABSTRACT

The Bregman divergence (Bregman distance, Bregman measure of distance) is a certain useful substitute for a distance, obtained from a well-chosen function (the ‘Bregman function’). Bregman functions and divergences have been extensively investigated during the last decades and have found applications in optimization, operations research, information theory, nonlinear analysis, machine learning and more. This paper re-examines various aspects related to the theory of Bregman functions and divergences. In particular, it presents many sufficient conditions which allow the construction of Bregman functions in a general setting and introduces new Bregman functions (such as a negative iterated log entropy). Moreover, it sheds new light on several known Bregman functions such as quadratic entropies, the negative Havrda-Charvát-Tsallis entropy, and the negative Boltzmann-Gibbs-Shannon entropy, and it shows that the negative Burg entropy, which is not a Bregman function according to the classical theory but nevertheless is known to have ‘Bregmanian properties’, can, by our re-examination of the theory, be considered as a Bregman function. Our analysis yields several by-products of independent interest such as the introduction of the concept of relative uniform convexity (a certain generalization of uniform convexity), new properties of uniformly and strongly convex functions, and results in Banach space theory.     

The Voronoi Diagram of Curved Objects

Voronoi diagrams of curved objects can show certain phenomena that are often considered artifacts: The Voronoi diagram is not connected; there are pairs of objects whose bisector is a closed curve or even a two-dimensional object; there are Voronoi edges between different parts of the same site (so-called self-Voronoi-edges); these self-Voronoi-edges may end at seemingly arbitrary points not on a site, and, in the case of a circular site, even degenerate to a single isolated point. We give a systematic study of these phenomena, characterizing their differential-geometric and topological properties. We show how a given set of curves can be refined such that the resulting curves define a “well-behaved” Voronoi diagram. We also give a randomized incremental algorithm to compute this diagram. The expected running time of this algorithm is O(n log n).     

Existence and convergence theorems for Bregman best proximity points in reflexive Banach spaces

In recent years, there has been considerable interest in the study of best proximity points. In this paper, using Bregman functions and Bregman distances, we first prove the existence of Bregman best proximity points in a reflexive Banach space. We then prove convergence results of Bregman best proximity points for Bregman cyclic contraction mappings in the setting of Banach spaces. It is well known that the Bregman distance does not satisfy either the symmetry property or the triangle inequality which are required for standard distances. So, Bregman distances enable us to provide affirmative answers to two problems raised by Eldred and Veeramani (J Math Anal Appl 323:1001–1006, 2006) and Al-Thagafi and Shahzad (Nonlinear Anal 70:3665–3671, 2009) concerning the existence of best proximity points for a cyclic contraction map in a reflexive Banach space. This can be done in the absence of either symmetry property or the triangle inequality which are required for standard distances. Our results improve and generalize many known results in the current literature.     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.     

A Generating Tree Approach to <Emphasis Type="Italic">k</Emphasis>-Nonnesting Partitions and Permutations

We describe a generating tree approach to the enumeration and exhaustive generation of k-nonnesting set partitions and permutations. Unlike previous work in the literature which uses the connections of these objects to Young tableaux and restricted lattice walks, our approach deals directly with partition and permutation diagrams. We provide explicit functional equations for the generating functions, with k as a parameter. Key to the solution is a superset of diagrams that permit semi-arcs. Many of the resulting counting sequences also count other well-known objects, such as Baxter permutations, and Young tableaux of bounded height.     

Klee sets and Chebyshev centers for the right Bregman distance

We systematically investigate the farthest distance function, farthest points, Klee sets, and Chebyshev centers, with respect to Bregman distances induced by Legendre functions. These objects are of considerable interest in Information Geometry and Machine Learning; when the Legendre function is specialized to the energy, one obtains classical notions from Approximation Theory and Convex Analysis.The contribution of this paper is twofold. First, we provide an affirmative answer to a recently-posed question on whether or not every Klee set with respect to the right Bregman distance is a singleton. Second, we prove uniqueness of the Chebyshev center and we present a characterization that relates to previous works by Garkavi, by Klee, and by Nielsen and Nock.     

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.

Voronoi diagrams and arrangements

We propose a uniform and general framework for defining and dealing with Voronoi diagrams. In this framework a Voronoi diagram is a partition of a domainD induced by a finite number of real valued functions onD. Valuable insight can be gained when one considers how these real valued functions partitionD ×R. With this view it turns out that the standard Euclidean Voronoi diagram of point sets inR ^d along with its order-k generalizations are intimately related to certain arrangements of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms. We also discuss how the formalism of arrangements can be used to solve certain intersection and union problems.     

Representable Functions on the Unit Ball of a Banach Space

In this paper we treat the problem of integral representation of analytic functions over the unit ball of a complex Banach space X using the theory of abstract Wiener spaces. We define the class of representable functions on the unit ball of X and prove that this set of functions is related with the classes of integral k–homogeneous polynomials, integral holomorphic functions and also with the set of L ^p –representable functions on a Banach space.     

Simplified Voronoi diagrams

We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in anr-dimensional space may be simplified to a search on an (r–1)-dimensional Voronoi diagram. We define a Voronoi diagramV based on a measure of distance which is not a true metric. This formulation has lower algebraic complexity than the usual definition, which is a considerable advantage in motion-planning problems with many degrees of freedom. In its simplest form, the measure of distance between a point and a polytope is the maximum of the distances of the point from the half-spaces which pass through faces of the polytope. More generally, the measure is defined in configuration spaces which represent rotation. The Voronoi diagram defined using this distance measure is no longer a strong deformation retract of free space, but it has the following useful property: any path through free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it has lower algebraic complexity than a diagram based on the Euclidean metric.This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's Artificial Intelligence research is provided in part by the Office of Naval Research under Office of Naval Research Contract N00014-81-K-0494 and in part by the Advanced Research Projects Agency under Office of Naval Research Contracts N00014-85-K-0124 and N00014-82-K-0334. John Canny was supported by an IBM fellowship. Bruce Donald was funded in part by a NASA fellowship administered by the Jet Propulsion Laboratory.     

Right Bregman nonexpansive operators in Banach spaces

We introduce and study new classes of Bregman nonexpansive operators in reflexive Banach spaces. These classes of operators are associated with the Bregman distance induced by a convex function. In particular, we characterize sunny right quasi-Bregman nonexpansive retractions, and as a consequence, we show that the fixed point set of any right quasi-Bregman nonexpansive operator is a sunny right quasi-Bregman nonexpansive retract of the ambient Banach space.     

On Bregman-Type Distances for Convex Functions and Maximally Monotone Operators

Given two point to set operators, one of which is maximally monotone, we introduce a new distance in their graphs. This new concept reduces to the classical Bregman distance when both operators are the gradient of a convex function. We study the properties of this new distance and establish its continuity properties. We derive its formula for some particular cases, including the case in which both operators are linear monotone and continuous. We also characterize all bi-functions D for which there exists a convex function h such that D is the Bregman distance induced by h.     

A new duality result concerning voronoi diagrams

A new duality between order-k Voronoi diagrams inE ^d and convex hulls inE ^d+1 is established. It implies a reasonably simple algorithm for computing the order-k diagram forn points in the plane inO(k ² n logn) time and optimalO(k(n–k)) space.Research was supported by the Austrian Fond zur Foerderung der wissenschaftlichen Forschung.     

A general algorithm for multiple-sets split feasibility problem involving resolvents and Bregman mappings

In this paper, by using Bregman distance, we introduce a new iterative process involving products of resolvents of maximal monotone operators for approximating a common element of the set of common fixed points of a finite family of multi-valued Bregman relatively nonexpansive mappings and the solution set of the multiple-sets split feasibility problem and common zeros of maximal monotone operators. We derive a strong convergence theorem of the proposed iterative algorithm under appropriate situations. Finally, we mention several corollaries and two applications of our algorithm.     

The fibres of the Scott map on polygon tilings are the flip equivalence classes

Monatshefte für Mathematik - We define a map from tilings of surfaces with marked points to strand diagrams, generalising Scott’s construction for the case of triangulations of polygons....     

Bregman distances and Chebyshev sets

A closed set of a Euclidean space is said to be Chebyshev if every point in the space has one and only one closest point in the set. Although the situation is not settled in infinite-dimensional Hilbert spaces, in 1932 Bunt showed that in Euclidean spaces a closed set is Chebyshev if and only if the set is convex. In this paper, from the more general perspective of Bregman distances, we show that if every point in the space has a unique nearest point in a closed set, then the set is convex. We provide two approaches: one is by nonsmooth analysis; the other by maximal monotone operator theory. Subdifferentiability properties of Bregman nearest distance functions are also given.     

A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces

Delaunay triangulations and Voronoi diagrams have found numerous applications in surface modeling, surface mesh generation, deformable surface modeling and surface reconstruction. Many algorithms in these applications begin by constructing the three-dimensional Delaunay triangulation of a finite set of points scattered over a surface. Their running-time therefore depends on the complexity of the Delaunay triangulation of such point sets. Although the complexity of the Delaunay triangulation of points in R³ may be quadratic in the worst case, we show in this paper that it is only linear when the points are distributed on a fixed set of well-sampled facets of R³ (e.g. the planar polygons in a polyhedron). Our bound is deterministic and the constants are explicitly given.     

On Nearest-Neighbor Graphs

The ``nearest-neighbor' relation, or more generally the ``k-nearest-neighbors' relation, defined for a set of points in a metric space, has found many uses in computational geometry and clustering analysis, yet surprisingly little is known about some of its basic properties. In this paper we consider some natural questions that are motivated by geometric embedding problems. We derive bounds on the relationship between size and depth for the components of a nearest-neighbor graph and prove some probabilistic properties of the k-nearest-neighbors graph for a random set of points. Received March 31, 1995, and in revised form August 11, 1996.