Higher-dimensional voronoi diagrams in linear expected time

A general method is presented for determining the mathematical expectation of the combinatorial complexity and other properties of the Voronoi diagram ofn independent and identically distributed points. The method is applied to derive exact asymptotic bounds on the expected number of vertices of the Voronoi diagram of points chosen from the uniform distribution on the interior of ad-dimensional ball; it is shown that in this case, the complexity of the diagram is ∵(n) for fixedd. An algorithm for constructing the Voronoid diagram is presented and analyzed. The algorithm is shown to require only ∵(n) time on average for random points from ad-ball assuming a real-RAM model of computation with a constant-time floor function. This algorithm is asymptotically faster than any previously known and optimal in the average-case sense. Based upon work supported by the National Science Foundation under Grant No. CCR-8658139 while the author was a student at Carnegie-Mellon University.     

On the construction of abstract voronoi diagrams

We show that the abstract Voronoi diagram ofn sites in the plane can be constructed in timeO(n logn) by a randomized algorithm. This yields an alternative, but simpler,O(n logn) algorithm in many previously considered cases and the firstO(n logn) algorithm in some cases, e.g., disjoint convex sites with the Euclidean distance function. Abstract Voronoi diagrams are given by a family of bisecting curves and were recently introduced by Klein [13]. Our algorithm is based on Clarkson and Shor's randomized incremental construction technique [7]. This work was supported by the DFG, Me 620/6, and ESPRIT P3075 ALCOM. A preliminary version of this paper has been presented at STACS '90, Rouen, France.     

On levels in arrangements and voronoi diagrams

This paper gives efficient, randomized algorithms for the following problems: (1) construction of levels of order 1 tok in an arrangement of hyperplanes in any dimension and (2) construction of higher-order Voronoi diagrams of order 1 tok in any dimension. A new combinatorial tool in the form of a mathematical series, called a θ series, is associated with an arrangement of hyperplanes inR ^d . It is used to study the combinatorial as well as algorithmic complexity of the geometric problems under consideration.     

On voronoi diagrams in theL p-metric in ℝD

We prove upper bounds on the number ofL _p-spheres passing throughD+1 points in general position in ℝ”, and on the sum of the Betti numbers of the intersection of bisectors in theL _p-metric, wherep is an even positive integer. The bounds found do not depend onp. Our result implies that the complexity of Voronoi diagrams (for point sites in general position) in theL _p-metric is bounded for increasingp. The proof for this upper bound involves the techniques of Milnor [12] and Thom [16] for finding a bound on the sum of the Betti numbers of algebraic varieties, but instead of the usual degree of polynomials we use their additive complexity, and apply results of Benedetti and Risler [2], [13]. Furthermore, we prove that inD dimensions and for evenp the number ofL _p-spheres passing throughD+1 points in general position is odd. In particular, combined with results of [8], [9], our results clarify the structure of Voronoi diagrams based on theL _p-metric (with evenp) in three dimensions. For the proof we use the theory of degree of continuous mappings in ℝ^D, which is a tool widely applied in nonlinear analysis [14]. This work was partially supported by Deutsche Forschungsgemeinschaft, Grant K1 655/2-1. A preliminary version of this paper was presented at the 11th Annual Symposium on Theoretical Aspects of Computer Science, France, 1994.     

A general duality result for precompact sets

In this paper we present an elementary proof of a general duality result for precompact sets which can be considered as a far-reaching generalization of a well-known result of Grothendieck on precompactness in dual systems. It is then shown that a number of known results can be deduced from it, amongst others a general form of the Arzela-Ascoli theorem and Grothendieck's duality theorem itself.     

A new characterization of Bergman–Schatten spaces and a duality result

Let denote the space of all upper triangular matrices A such that lim_r→1⁻(1−r²)(A*C(r))^′_B(ℓ²)=0. We also denote by the closed Banach subspace of consisting of all upper triangular matrices whose diagonals are compact operators. In this paper we give a duality result between and the Bergman–Schatten spaces . We also give a characterization of the more general Bergman–Schatten spaces , 1p<∞, in terms of Taylor coefficients, which is similar to that of M. Mateljevic and M. Pavlovic [M. Mateljevic, M. Pavlovic, L^p-behaviour of the integral means of analytic functions, Studia Math. 77 (1984) 219–237] for classical Bergman spaces.     

A consistency result concerning set mappings

Research supported by Hungarian National Science Foundation Grant No. 1908 and 2117.     

A result concerning classes of matrices

This paper is concerned with the n-dimensional integral representations of an order in an algebraic number field of degree n, and their composition.     

A uniqueness result concerning Schur ideals

A subset of the set of all positive semi-definite matrices of a given size which is invariant under Schur (componentwise) multiplication by an arbitrary positive semi-definite matrix is said to be a Schur ideal. A subset of -dimensional complex space is said to be if it arises as the set of possible values arising from restricting contractive elements from some uniform algebra to a finite set in the domain. When the uniform algebra is the disk algebra, the hyperconvex set is said to be a Pick body. Motivated by the classical Pick interpolation theorem, Paulsen has introduced a natural notion of duality between Schur ideals and hyperconvex sets. By using some recently developed results in operator algebras (matricial Schur ideals), we show that each Pick body has a unique affiliated Schur ideal.

     

A new duality transform

Continuing our search for dualities in different classes of functions, which usually turn out to have an essentially unique form, depending on the class, we exhibit a natural class of functions for which there are exactly two different types of duality transforms. One is the well known Legendre transform, and the other is new. We study the new transform, give a simple geometric interpretation for it, and present some applications. To cite this article: S. Artstein-Avidan, V. Milman, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

A stability result concerning the Shannon entropy

Summary. We are concerned with a well-known characterization of the Shannon entropy by Faddeev, suitably re-examined in the frame of Ulam--Hyers "stability" of functional equations.¶By use of some results about number theoretical functions, we give a sufficient condition that the solutions of a suitable system of countably many functional inequalities approximate the Shannon entropy uniformly.     

Generalized voronoi diagrams for moving a ladder. I: Topological analysis

Given a bounded open subset Ω of the plane whose boundary is the union of finitely many polygons, and a real number d > 0, a manifold FP (the [free placements]) may be defined as the set of placements of a closed oriented line-segment B (a [ladder]) of length d inside Ω. FP is a three-dimensional manifold. A [Voronoi complex] in this manifold, a two-dimensional cell complex, is defined by analogy with the classical geometric construction in the plane; within this complex a one-dimensional subcomplex N, called the skeleton, is defined. It is shown that every component of FP contains a unique component of N, and canonical motions are given to move the ladder to placements within N. In this way, general motion planning is reduced to searching in a suitable representation of N as a (combinatorial) graph. Efficient construction of N is described in a companion paper.     

A result in surrogate duality for certain integer programming problems

We consider linear programming problems with some equality constraints. For such problems, surrogate relaxation formulations relaxing equality constraints existwith zero primal-dual gap both when all variables are restricted to be integers and when no variable is required to be integer. However, for such surrogate formulations, when the variables are mixed-integer, the primal-dual gap may not be zero. We establish this latter result by a counterexample.     

A new duality theory for compact groups

Summary The Tannaka-Krein duality theory characterizes the category (G) of finite-dimensional, continuous, unitary representations of a compact group as a subcategory of the category of Hilbert spaces. We prove a more powerful result characterizing (G) as an abstract category: every strict symmetric monoidalC ^*-category with conjugates which has subobjects and direct sums and for which theC ^*-algebra of endomorphisms of the monoidal unit reduces to the complex numbers is isomorphic to a category (G) for a compact groupG unique up to isomorphism.Research supported by the Ministero della Pubblica Istruzione and CNR-GNAFA     

A stability result concerning the obstacle problem for a plate

It is proposed here to study the free boundary of the obstacle problem in the case of an elastic plate. Under a nondegeneracy assumption, we prove a stability theorem which relates the variations of the contact zone to the variations the external forces. The statement of this result obtained and the steps in the proof are very close to those given by D.G. Schaeffer in 1975, except for the very important fact that the present study deals with the biharmonic operator.     

A stability result concerning the obstacle problem for a plate

It is proposed here to study the free boundary of the obstacle problem in the case of an elastic plate. Under a nondegeneracy assumption, we prove a stability theorem which relates the variations of the contact zone to the variations the external forces. The statement of this result obtained and the steps in the proof are very close to those given by D.G. Schaeffer in 1975, except for the very important fact that the present study deals with the biharmonic operator.