Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions

The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if S is a set of n points in general position in R ^d , the maximum complexity of its Voronoi diagram under the L _∞ metric, and also under a simplicial distance function, are both shown to be . The upper bound for the case of the L _∞ metric follows from a new upper bound, also proved in this paper, on the maximum complexity of the union of n axis-parallel hypercubes in R ^d . This complexity is , for d ≥ 1 , and it improves to , for d ≥ 2 , if all the hypercubes have the same size. Under the L ₁ metric, the maximum complexity of the Voronoi diagram of a set of n points in general position in R ³ is shown to be . We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations. (This increase does not occur with an appropriate modification of the diagram definition.) Finally, on-line algorithms are proposed for computing the Voronoi diagram of n points in R ^d under a simplicial or L _∞ distance function. Their expected randomized complexities are for simplicial diagrams and for L _∞ -diagrams. Received July 31, 1995, and in revised form September 9, 1997.     

Generalized Cranston-McConnell inequalities and Martin boundaries of unbounded domains

LetD be a domain inR ² with the Green functionG(x, y) for the Laplace equation. We give a generalization of the Cranston-McConnell inequality concerning the integrability of positive harmonic functions onD. A typical new inequality is {fx137-01} whereu andv ₁,..., v_nare positive superharmonic functions onD andc _nis a constant depending only onn. The generalized Cranston-McConnell inequality is used for the determination of the Martin boundary of a certain unbounded domain.     

On directional convexity

Motivated by problems from calculus of variations and partial differential equations, we investigate geometric properties of D-convexity. A function f: R ^d → R is called D-convex, where D is a set of vectors in R ^d, if its restriction to each line parallel to a nonzero v ∈ D is convex. The D-convex hull of a compact set A ⊂ R ^d, denoted by co^D(A), is the intersection of the zero sets of all nonnegative D-convex functions that are zero on A. It also equals the zero set of the D-convex envelope of the distance function of A. We give an example of an n-point set A ⊂ R ² where the D-convex envelope of the distance function is exponentially close to zero at points lying relatively far from co ^D(A), showing that the definition of the D-convex hull can be very nonrobust. For separate convexity in R ³ (where D is the orthonormal basis of R ³), we construct arbitrarily large finite sets A with co ^D(A) ≠ A whose proper subsets are all equal to their D-convex hull. This implies the existence of analogous sets for rank-one convexity and for quasiconvexity on 3 × 3 (or larger) matrices. This research was supported by Charles University Grants No. 158/99 and 159/99.     

Study of Hopficity in Certain Classes of Rings

The main results proved in this paper are:

1. For any non-zero vector space V _Dover a division ring D, the ring R= End(V _D) is hopfian as a ring

2. Let Rbe a reduced π-regular ring &; B(R) the boolean ring of idempotents of R. If B(R) is hopfian so is R.The converse is not true even when Ris strongly regular.

3. Let Xbe a completely regular spaceC(X) (resp. C ^?(X)) the ring of real valued (resp. bounded real valued) continuous functions on X. Let Rbe any one of C(X) or C ^?(X). Then Ris an exchange ring if &; only if Xis zero dimensional in the sense of Katetov. for any infinite compact totally disconnected space X C(X) is an exchange ring which is not von Neumann regular.

4. Let Rbe a reduced commutative exchange ring. If Ris hopfian so is the polynomial ring R[T ₁,…,T _n] in ncommuting indeterminates over Rwhere nis any integer ≥ 1.

5. Let Rbe a reduced exchange ring. If Ris hopfian so is the polynomial ring R[T].     

On global integrability of BMO functions on general domains

Extending results of Staples and Smith-Stegenga, we characterize measurable subsets of a given domainD ⊃R ⁿ on which BMO(D) functions areL ^p integrable or exponentially integrable. In particular, we characterize uniform domains by the integrability of BMO functions. We also remark on the boundedness of domains satisfying a certain integrability condition for the quasihyperbolic metric.     

Discontinuity of Best Harmonic Approximants

LetDR²be the open unit disk. We consider best harmonic approximation to functions continuous onD. In a basic paper, Haymanet al.characterized best harmonic approximants which are themselves continuous onD. In this paper we give sufficient conditions and many simple examples of functions continuous onDwhich have no best harmonic approximants which are continuous onD.     

An active index algorithm for the nearest point problem in a polyhedral cone

We consider the problem of finding the nearest point in a polyhedral cone C={x∈R ⁿ :D x≤0} to a given point b∈R ⁿ , where D∈R ^m×n . This problem can be formulated as a convex quadratic programming problem with special structure. We study the structure of this problem and its relationship with the nearest point problem in a pos cone through the concept of polar cones. We then use this relationship to design an efficient algorithm for solving the problem, and carry out computational experiments to evaluate its effectiveness. Our computational results show that our proposed algorithm is more efficient than other existing algorithms for solving this problem.     

Radial Multiresolution, Cuntz Algebras Representations and an Application to Fractals

We study Bernoulli type convolution measures on attractor sets arising from iterated function systems on R. In particular we examine orthogonality for Hankel frequencies in the Hilbert space of square integrable functions on the attractor coming from a radial multiresolution analysis on R³. A class of fractals emerges from a finite system of contractive affine mappings on the zeros of Bessel functions. We have then fractal measures on one hand and the geometry of radial wavelets on the other hand. More generally, multiresolutions serve as an operator theoretic framework for the study of such selfsimilar structures as wavelets, fractals, and recursive basis algorithms. The purpose of the present paper is to show that this can be done for a certain Bessel–Hankel transform. Submitted: February 20, 2008., Accepted: March 6, 2008.     

Standardness of *-representations of the algebra of smooth finite functions

We study strongly continuous *-representations by unbounded operators of the algebra of smooth finite functions on R^N. We establish that the closure of a strongly continuous *-representation of the algebraD(R^N), satisfying a certain condition, is self-adjoint and standard. We also study the correspondence between the strongly continuous *-representations ofD(R^N) and the continuous representations of the group R^N with respect to addition by symmetric operators.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 5, pp. 713–716, May, 1990.     

Distribution of values of a real function means,moments, and symmetry

For a distribution functionD we define itsabsolute andsigned moments of orderk∈R, which generalise in a natural way the Hamburger moments of orders an even and an odd natural number. Similarly, for a real functionh we define itsabsolute andsigned asymptotic means of orderk∈R. We show that if the means exist on an infinite and bounded set of values ofk, then they exist on an intervalI and coincide onI ^o with the moments ofD=D _h, the distribution function of the values ofh, which is shown to exist (in the sense of Wintner). We also give a sufficient condition forD _h to be symmetric. These results apply to a class of functionsh that contain in particular error terms related to the Euler phi function and to the sigma divisor function. A further application on a certain class of converging trigonometrical series implies in particular classical results of A. Wintner establishing the existence for such functions of a distribution function as well as Hamburger moments of arbitrarily large orders. The remainder term of the prime number theorem belongs to this class provided the Riemann hypothesis holds, and the distribution function of its values is shown to be “almost” symmetric.     

Upper bounds of small Eigenvalues of the Dirac operator and isometric immersions

We show that a topologically determined number of eigenvalues of the Dirac operatorD of a closed Riemannian spin manifoldM of even dimensionn can be bounded by the data of an isometric immersion ofM into the Euclidian spaceR ^N . From this we obtain similar bounds of the eigenvalues ofD in terms of the scalar curvature ofM ifM admits a minimal immersion intoS ^N or,ifM is complex, a holomorphic isometric immersion intoPC ^N .     

On Functional Separately Convex Hulls

Let D be a set of vectors in R ^d . A function f: R ^d → R is called D-convex if its restriction to each line parallel to a nonzero vector of D is a convex function. For a set A⊆ R ^d , the functional D-convex hull of A, denoted by co ^D (A) , is the intersection of the zero sets of all nonnegative D -convex functions that are 0 on A . We prove some results concerning the structure of functional D -convex hulls, e.g., a Krein—Milman-type theorem and a result on separation of connected components. We give a polynomial-time algorithm for computing co ^D (A) for a finite point set A (in any fixed dimension) in the case of D being a basis of R ^d (the case of separate convexity). This research is primarily motivated by questions concerning the so-called rank-one convexity, which is a particular case of D -convexity and is important in the theory of systems of nonlinear partial differential equations and in mathematical modeling of microstructures in solids. As a direct contribution to the study of rank-one convexity, we construct a configuration of 20 symmetric 2 x 2 matrices in a general (stable) position with a nontrivial functionally rank-one convex hull (answering a question of K. Zhang on the existence of higher-dimensional nontrivial configurations of points and matrices). Received October 3, 1995, and in revised form June 24, 1996.     

Square area integral estimates for subharmonic functions in NTA domains

In this paper, we prove a good-λ inequality between the nontangential maximal function and the square area integral of a subharmonic functionu in a bounded NTA domainD inR ⁿ . We achieve this by showing that a weighted Riesz measure ofu is a Carleson measure, with the Carleson norm bounded by a constant independent ofu. As consequences of the good-λ inequality, we obtain McConnell-Uchiyama's inequality and an analogue of Murai-Uchiyama's inequality for subharmonic functions inD.     

Characterization of Multidimensional Stable Random Measures by Means of Vector Measures

Abstract

In connection with a symmetric α stable random measure Φ on a measurable space (F, ?) with values in R ^d , a complete metric space of symmetric finite measures on S _d?1 is constructed, and is employed to characterize the law of Φ by a unique positive measure on ? and a unique function on F × R ^d . The stochastic integral ∫ _F f d Φ is also defined for certain d × d matrix valued functions f, which for α = 2 reduces to the Wiener–Masani integral.     

Bregman Voronoi Diagrams

The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given object than to the others. We may define various variants of Voronoi diagrams depending on the class of objects, the distance function and the embedding space. In this paper, we investigate a framework for defining and building Voronoi diagrams for a broad class of distance functions called Bregman divergences. Bregman divergences include not only the traditional (squared) Euclidean distance but also various divergence measures based on entropic functions. Accordingly, Bregman Voronoi diagrams allow one to define information-theoretic Voronoi diagrams in statistical parametric spaces based on the relative entropy of distributions. We define several types of Bregman diagrams, establish correspondences between those diagrams (using the Legendre transformation), and show how to compute them efficiently. We also introduce extensions of these diagrams, e.g., k-order and k-bag Bregman Voronoi diagrams, and introduce Bregman triangulations of a set of points and their connection with Bregman Voronoi diagrams. We show that these triangulations capture many of the properties of the celebrated Delaunay triangulation.     

ON THE SEPARATION PROPERTY OF SYMMETRIC ORDINARY SECOND-ORDER DIFFERENTIAL EXPRESSIONS

A 1-variable calculus type argument is used to show that, for a function f : R ² → R, if for all (a, b) ? R ² we have that f o c is smooth for every smooth curve c : R → R ² nonsingular except at 0 and with c(0) = (a, b), then f is smooth. This strengthens Boman's theorem. In fact, we use an even more special collection of smooth curves to prove Boman's theorem. It is shown using a related special collection of smooth curves how the upper half cone can be viewed largely as a model for polar coordinates. Our proof here shows how the use of Frölicher spaces can reduce questions in several dimensions to those of one real variable.     

The maximal conjugate and Hilbert operators on real Hardy spaces

Summary We prove that the maximal conjugate and Hilbert operators are not bounded from the real Hardy space H¹ to L¹, where the underlying spaces may be over T or R. We also draw corollaries for the corresponding spaces over T² and R².     

Totally real embeddings of the torus intoC 2

In this short note we combine a construction of Viro and a result of Eliashberg and Harlamov to prove that there exist smooth totally real embeddings of the torus intoC ² which are isotopic but not so within the class of totally real surfaces. We also show how Viro's construction can be used to define an isotopy invariant for a certain class of complex curves inC P ².     

On levi–typ conditions for hypoellipticity of certain diffrential operators

The hypoelliticity is discussed for operators of the form P=D² _x+a(x)D² _y+b(x)D_ywhere a (x) and b (x) are real–valued C^∞ functions satisfying a(0)=0 and a(x) >0 for x≠0.We seek the conditions for P to be hypoelliptic, especially in the case where both a (x) and b(x) vanish to infinite order on x=0.     

ON THE MINIMUM INTRINSIC 1-VOLUME OF VORONOI CELLS IN LATTICE UNIT SPHERE PACKINGS

A typical 3-dimensional (in short '3D') Voronoi cell of a 3Dlattice has six families of parallel edges. We call any six representants of these six families the generating edges of the Voronoi cell. The sum s of lengths of generating edges of a Voronoi-cell of a lattice unit sphere packing in the 3-dimensional Euclidean space is a special case of intrinsic 1-volumes of 3Dzonotopes with inradius 1 which are investigated accurately in [B]. However, the minimum of this value is unknown even in this special case. As the regular rhombic dodecahedron shows optimal properties in many similar problems, it was reasonable to conjecture that it also has the minimal s value. In this note we present a construction of a lattice unit ball packing whose Voronoi cell possesses an intrinsic 1-volume strictly less than the one of the proper regular rhombic dodecahedron, hence providing a smaller upper bound for s than it was conjectured. A further issue of the note is a formula for edge-lengths of Voronoi cells of lattice unit ball packings that can be used efficiently in similar calculations. This revised version was published online in August 2006 with corrections to the Cover Date.