Separating subadditive euclidean functionals

The classical Beardwood‐Halton‐Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form for the minimum length of a Traveling Salesperson Tour throuh n random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such Euclidean functionals on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through n random points in was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2‐factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch‐and‐bound algorithms based on these natural lower bounds must take nearly exponential () time to solve the TSP to optimality, even in average case. This is the first average‐case superpolynomial lower bound for these branch‐and‐bound algorithms (a lower bound as strong as was not even been known in worst‐case analysis). © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 375–403, 2017     

On the structure of quadratic congruential sequences

Sequences of integers defined by a quadratic congruential formula are divided into non-overlapping subsequences of length d. The structure of the set of the resulting points in the d-dimensional Euclidean space R^d is studied. The analysis is restricted to the case of sequences with maximal period length since such sequences are of special interest in connection with pseudo random number generation.     

Euclidean semi-matchings of random samples

A linear programming relaxation of the minimal matching problem is studied for graphs with edge weights determined by the distances between points in a Euclidean space. The relaxed problem has a simple geometric interpretation that suggests the name minimal semi-matching. The main result is the determination of the asymptotic behavior of the length of the minimal semi-matching. It is analogous to the theorem of Beardwood, Halton and Hammersley (1959) on the asymptotic behavior of the traveling salesman problem. Associated results on the length of non-random Euclidean semi-matchings and large deviation inequalities for random semi-matchings are also given.Research supported in part by NSF Grant #DMS-8812868, ARO contract DAAL03-89-G-0092.P001, AFOSR-89-08301.A and NSA-MDA-904-89-2034.     

On stochastic generation of ultrametrics in high-dimensional Euclidean spaces

We present a proof of the theorem which states that a matrix of Euclidean distances on a set of specially distributed random points in the n-dimensional Euclidean space R ⁿ converges in probability to an ultrametric matrix as n → ∞. Values of the elements of an ultrametric distance matrix are completely determined by variances of coordinates of random points. Also we present a probabilistic algorithm for generation of finite ultrametric structures of any topology in high-dimensional Euclidean space. Validity of the algorithm is demonstrated by explicit calculations of distance matrices and ultrametricity indexes for various dimensions n.     

A study on densities of sets of points and lines

In this paper, firstly, our purpose is to give the relationship among the densities of the sets of collinear points, the relationship among the densities of the sets of noncollinear points, and the relationship among the densities of the sets of the intersecting lines in Euclidean plane, respectively. In addition to that, we define the density formulas for the sets of points and lines under the two‐parameter planar Euclidean motion. By means of these results, we obtain essential properties that explain the connection among the densities of the sets of points and among the densities of the sets of intersecting lines under the two‐parameter planar Euclidean motion.     

Distribution of size,structure and number of vacant regions in a high-intensity mosaic

Summary A mosaic is formed by centring independent and identically distributed random sets at points of a Poisson process in Euclidean space. We derive high-intensity approximations to the distributions of size, structure and number of uncovered regions in a mosaic. A limit theorem is proved for vacancy, and leads to a general approximation to the probability that a given region is completely covered by random shapes.     

A CLT concerning critical points of random functions on a Euclidean space

We prove a central limit theorem concerning the number of critical points in large cubes of an isotropic Gaussian random function on a Euclidean space.     

Limit theory for the random on‐line nearest‐neighbor graph

In the on‐line nearest‐neighbor graph (ONG), each point after the first in a sequence of points in ?^d is joined by an edge to its nearest neighbor amongst those points that precede it in the sequence. We study the large‐sample asymptotic behavior of the total power‐weighted length of the ONG on uniform random points in (0,1)^d. In particular, for d = 1 and weight exponent α > 1/2, the limiting distribution of the centered total weight is characterized by a distributional fixed‐point equation. As an ancillary result, we give exact expressions for the expectation and variance of the standard nearest‐neighbor (directed) graph on uniform random points in the unit interval. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The cut‐tree of large trees with small heights

We destroy a finite tree of size n by cutting its edges one after the other and in uniform random order. Informally, the associated cut‐tree describes the genealogy of the connected components created by this destruction process. We provide a general criterion for the convergence of the rescaled cut‐tree in the Gromov‐Prohorov topology to an interval endowed with the Euclidean distance and a certain probability measure, when the underlying tree has branching points close to the root and height of order . In particular, we consider uniform random recursive trees, binary search trees, scale‐free random trees and a mixture of regular trees. This yields extensions of a result in Bertoin (Probab Stat 5 (2015), 478–488) for the cut‐tree of uniform random recursive trees and also allows us to generalize some results of Kuba and Panholzer (Online J Anal Combin (2014), 26) on the multiple isolation of vertices. The approach relies in the close relationship between the destruction process and Bernoulli bond percolation, which may be useful for studying the cut‐tree of other classes of trees. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 404–427, 2017     

Central limit theorems for the radial spanning tree

Consider a homogeneous Poisson point process in a compact convex set in d‐dimensional Euclidean space which has interior points and contains the origin. The radial spanning tree is constructed by connecting each point of the Poisson point process with its nearest neighbour that is closer to the origin. For increasing intensity of the underlying Poisson point process the paper provides expectation and variance asymptotics as well as central limit theorems with rates of convergence for a class of edge functionals including the total edge length. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 262–286, 2017     

Limit behaviors of random connected graphs driven by a Poisson process

We consider a class of random connected graphs with random vertices and random edges with the random distribution of vertices given by a Poisson point process with the intensity n localized at the vertices and the random distribution of the edges given by a connection function. Using the Avram-Bertsimas method constructed in 1992 for the central limit theorem on Euclidean functionals, we find the convergence rate of the central limit theorem process, the moderate deviation, and an upper bound for large deviations depending on the total length of all edges of the random connected graph.     

On the relative distances of seven points in a plane convex body

Let C be a convex body in the Euclidean plane. The relative distance of points p and q is twice the Euclidean distance of p and q divided by the Euclidean length of a longest chord in C with the direction, say, from p to q. We prove that, among any seven points of a plane convex body, there are two points at relative distance at most one, and one cannot be replaced by a smaller value. We apply our result to determine the diameter of point sets in normed planes. Zsolt Lángi: Partially supported by the Hung. Nat. Sci. Found. (OTKA), grant no. T043556 and T037752 and by the Alberta Ingenuity Fund.     

The steiner ratio for five points

It was conjectured by Gilbert and Pollak [5] that for any finite set of points in the Euclidean plane, the ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree is at least 3/2. The present paper proves the conjecture for five points, using a formula for the length of full Steiner trees.     

Expected Distances between Two Uniformly Distributed Random Points in Rectangles and Rectangular Parallelpipeds

In this paper, the expected distance between two uniformly distributed random points in a rectangle or in a rectangular parallelepiped is computed under three different metrics: the Manhattan metric, the Euclidean metric, and the Chebychev metric.     

Heuristics for the Stochastic Eulerian Tour Problem

The Stochastic Eulerian Tour Problem (SETP) seeks the Eulerian tour of minimum expected length on an undirected Eulerian graph, when demand on the arcs that have to be serviced is probabilistic. The SETP is NP-hard and in this paper, we develop three constructive heuristics for this problem. The first two are greedy tour construction heuristics while the third is a sub-tour concatenation heuristic. Our experimental results show that for grid networks, the sub-tour concatenation heuristic performs well when the probability of service of each edge is greater than 0.1. For Euclidean networks, as the number of edges increases, the second heuristic performs the best among the three. Also, the expected length of our overall best solution is lower than the expected length of a random tour by up to 10% on average for grid networks and up to 2% for Euclidean networks.     

Spectral localization for quantum Hamiltonians with weak random delta interaction

We consider a negative Laplacian in multi-dimensional Euclidean space (or a multi-dimensional layer) with a weak disorder random perturbation. The perturbation consists of a sum of lattice translates of a delta interaction supported on a compact manifold of co-dimension one and modulated by coupling constants, which are independent identically distributed random variables times a small disorder parameter. We establish that the spectrum of the considered operator is almost surely a fixed set, characterize its minimum, give an initial length scale estimate and the Wegner estimate, and conclude that there is a small zone of a pure point spectrum containing the almost sure spectral bottom. The length of this zone is proportional to the small disorder parameter.     

Two Heuristics for the Euclidean Steiner Tree Problem

The Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics are desired. We present two such heuristics, both of which utilize an efficient method for computing a locally optimal tree with a given topology. The first systematically inserts Steiner points between edges of the minimal spanning tree meeting at angles less than 120 degrees, performing a local optimization at the end. The second begins by finding the Steiner tree for three of the fixed points. Then, at each iteration, it introduces a new fixed point to the tree, connecting it to each possible edge by inserting a Steiner point, and minimizes over all connections, performing a local optimization for each. We present a variety of test cases that demonstrate the strengths and weaknesses of both algorithms. This revised version was published online in July 2006 with corrections to the Cover Date.     

On the central limit theorem for the stationary Poisson process of compact sets

Stochastic geometry models based on a stationary Poisson point process of compact subsets of the Euclidean space are examined. Random measures on ?^d, derived from these processes using Hausdorff and projection measures are studied. The central limit theorem is formulated in a way which enables comparison of the various estimators of the intensity of the produced random measures. Approximate confidence intervals for the intensity are constructed. Their use is demonstrated in an example of length intensity estimation for the segment processes. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Surface tensor estimation from linear sections

From Crofton's formula for Minkowski tensors we derive stereological estimators of translation invariant surface tensors of convex bodies in the n‐dimensional Euclidean space. The estimators are based on one‐dimensional linear sections. In a design based setting we suggest three types of estimators. These are based on isotropic uniform random lines, vertical sections, and non‐isotropic random lines, respectively. Further, we derive estimators of the specific surface tensors associated with a stationary process of convex particles in the model based setting.     

有限点集的m级连心线及其性质(英文)

In this paper, we first give the concept of m-degree center-connecting line in n-dimensional Euclidean space Enand investigate its several properties, then we obtain the length of m-degree center-connecting line formula in finite points set. As its application,we extend the Leibniz formula and length of medians formula in n-dimensional simplex to polytope.