Combinatorial aspects of geometric graphs

As a special case of our main result, we show that for all L> 0, each k-nearest neighbor graph in d dimensions excludes K_h as a depth L minor if h = Ω(L^d). More generally, we prove that the overlap graphs defined by Miller, Teng, Thurston and Vavasis (1993) have this combinatorial property. By a construction of Plotkin, Rao and Smith (1994), our result implies that overlap graphs have “good” cut-covers, answering an open question of Kaklamanis, Krizanc and Rao (1993). Consequently, overlap graphs can be emulated on hypercube graphs with a constant factor of slow-down and on butterfly graphs with a factor of O(log^* n) slow-down. Therefore, computations on overlap graphs, such as finite element and finite difference methods on “well-conditioned” meshes and image processing on k-nearest neighbor graphs, can be performed on hypercubic parallel machines with a linear speed-up. Our result, in conjunction with a result of Plotkin, Rao and Smith, also yields a combinatorial proof that overlap graphs have separators of sublinear size. We also show that with high probability, the Delaunay diagram, the relative neighborhood graph, and the k-nearest neighbor graph of a random point set exclude K_h as a depth L minor if h = Ω(L^d/2 log n).     

On determining the congruence of point sets in d dimensions

This paper considers the following problem: given two point sets A and B (|A| = |B| = n) in d dimensional Euclidean space, determine whether or not A is congruent to B. This paper presents an O(n^(d−1)/2 log n) time randomized algorithm. The birthday paradox, which is well-known in combinatorics, is used effectively in this algorithm. Although this algorithm is Monte-Carlo type (i.e., it may give a wrong result), this improves a previous O(n^d−2 log n) time deterministic algorithm considerably. This paper also shows that if d is not bounded, the problem is at least as hard as the graph isomorphism problem in the sense of the polynomiality. Several related results are described too.     

Dynamic motion planning in low obstacle density environments

A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and realistic low obstacle density (L.O.D.) assumption results in linear complexity in the number of obstacles of the free space (Van der Stappen et al., 1997). In this paper we address the dynamic version of the motion planning problem in which a robot moves among polygonal obstacles which move along polylines. The obstacles are assumed to move along constant complexity polylines, and to respect the low density property at any given time. We will show that in this situation a cell decomposition of the free space of size O(n²(n) log² n) can be computed in O(n²(n) log² n) time. The dynamic motion planning problem is then solved in O(n²(n) log³ n) time. We also show that these results are close to optimal.     

Popular distances in 3-space

Let m(n) denote the smallest integer m with the property that any set of n points in Euclidean 3-space has an element such that at most m other elements are equidistant from it. We have that cn^1/3 log log n m(n) n^3/5 β(n), where c> 0 is a constant and β(n) is an extremely slowly growing function, related to the inverse of the Ackermann function.     

Computing rectangle enclosures

The rectangle enclosure problem is the problem of determining the subset of n iso-oriented planar rectangles that enclose a query rectangle Q. In this paper, we use a three layered data structure which is a combination of Range and Priority search trees and answers both the static and dynamic cases of the problem. Both the cases use O(n> log² n) space. For the static case, the query time is O(log² n log log n + K). The dynamic case is supported in O(log³ n + K) query time using O(log³ n) amortized time per update. K denotes the size of the answer. For the d-dimensional space the results are analogous. The query time is O(log^2d-2 n log log n + K) for the static case and O(log^2d-1 n + K) for the dynamic case. The space used is O(n> log^2d-2 n) and the amortized time for an update is O(log^2d-1 n). The existing bounds given for a class of problems which includes the present one, are O(log^2d n + K) query time, O(log^2d n) time for an insertion and O(log^2d-1 n) time for a deletion.     

A characterization on n-critical economical generalized tic-tac-toe games

There is a so called generalized tic-tac-toe game playing on a finite set X with winning sets A₁, A₂,…, A_m. Two players, F and S, take in turn a previous untaken vertex of X, with F going first. The one who takes all the vertices of some winning set first wins the game. Erd s and Selfridge proved that if |A₁|=|A₂|==|A_m|=n and m<2ⁿ⁻¹, then the game is a draw. This result is best possible in the sense that once m=2ⁿ⁻¹, then there is a family A₁, A₂,…, A_m so that F can win. In this paper we characterize all those sets A₁,…, A_2n−1 so that F can win in exactly n moves. We also get similar result in the biased games.     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

Minimal enclosing parallelepiped in 3D

We investigate the problem of finding a minimal volume parallelepiped enclosing a given set of n three-dimensional points. We give two mathematical properties of these parallelepipeds, from which we derive two algorithms of theoretical complexity O(n⁶). Experiments show that in practice our quickest algorithm runs in O(n²) (at least for n10⁵). We also present our application in structural biology.     

Scaling exponents of random walks in random sceneries

We compute the exact asymptotic normalizations of random walks in random sceneries, for various null recurrent random walks to the nearest neighbours, and for i.i.d., centered and square integrable random sceneries. In each case, the standard deviation grows like n with . Here, the value of the exponent is determined by the sole geometry of the underlying graph, as opposed to previous examples, where this value reflected mainly the integrability properties of the steps of the walk, or of the scenery. For discrete Bessel processes of dimension d[0;2[, the exponent is . For the simple walk on some specific graphs, whose volume grows like n^d for d[1;2[, the exponent is =1−d/4. We build a null recurrent walk, for which without logarithmic correction. Last, for the simple walk on a critical Galton–Watson tree, conditioned by its nonextinction, the annealed exponent is . In that setting and when the scenery is i.i.d. by levels, the same result holds with .     

Forcing matchings on square grids

Let G be a graph that admits a perfect matching. The forcing number of a perfect matching M of G is defined as the smallest number of edges in a subset S M, such that S is in no other perfect matching. We show that for the 2n × 2n square grid, the forcing number of any perfect matching is bounded below by n and above by n². Both bounds are sharp. We also establish a connection between the forcing problem and the minimum feedback set problem. Finally, we present some conjectures about forcing numbers in other graphs.     

The coordinate representation of a graph and n-universal graph of radius 1

Every graph can be represented as the intersection graph on a family of closed unit cubes in Euclidean space Eⁿ. Cube vertices have integer coordinates. The coordinate matrix, A(G)={v_nk} of a graph G is defined by the set of cube coordinates. The imbedded dimension of a graph, Bp(G), is a number of columns in matrix A(G) such that each of them has at least two distinct elements v_nk≠v_pk. We show that Bp(G)=cub(G) for some graphs, and Bp(G)n−2 for any graph G on n vertices. The coordinate matrix uses to obtain the graph U of radius 1 with 3ⁿ⁻² vertices that contains as an induced subgraph a copy of any graph on n vertices.     

Upper bounds for nearly optimal diagonal scaling of matrices

Optimal diagonal scaling of an n×n matrix A consists in finding a diagonal matrix D that minimizes a condition number of AD. Often a nearly optimal scaling of A is achieved by taking a diagonal matrix D₁ such that all diagonal elements of D₁A^TAD₁ are equal to one. It is shown in this paper that the condition number of AD₁ can be at least (n/2)^1/2 times the minimal one. Some questions for a further research are posed.     

On the generalized Erdös-Szekeres Conjecture — a new upper bound

We prove the following result: For every two natural numbers n and q, n q + 2, there is a natural number E(n, q) satisfying the following:

1. (1) Let S be any set of points in the plane, no three on a line. If |S| E(n, q), then there exists a convex n-gon whose points belong to S, for which the number of points of S in its interior is 0 (mod q).

2. (2) For fixed q, E(n,q) 2^c(q)·n, c(q) is a constant depends on q only.

Part (1) was proved by Bialostocki et al. [2] and our proof is aimed to simplify the original proof. The proof of Part (2) is completely new and reduces the huge upper bound of [2] (a super-exponential bound) to an exponential upper bound.     

Proof of a conjecture of Fiedler and Markham

Let A be an n×n nonsingular M-matrix. For the Hadamard product AA⁻¹, M. Fiedler and T.L. Markham conjectured in [Linear Algebra Appl. 10l (1988) 1] that q(AA⁻¹)2/n, where q(AA⁻¹) is the smallest eigenvalue (in modulus) of AA⁻¹. We considered this conjecture in [Linear Algebra Appl. 288 (1999) 259] having observed an incorrect proof in [Linear Algebra Appl. 144 (1991) 171] and obtained that q(AA⁻¹)(2/n)(n−1)/n. The present paper gives a proof for this conjecture.     

Unavoidable doubly connected large graphs

A connected graph is doubly connected if its complement is also connected. The following Ramsey-type theorem is proved in this paper. There exists a function h(n), defined on the set of integers exceeding three, such that every doubly connected graph on at least h(n) vertices must contain, as an induced subgraph, a doubly connected graph, which is either one of the following graphs or the complement of one of the following graphs:

(1) P_n, a path on n vertices;

(2) K_1,n^s, the graph obtained from K_1,n by subdividing an edge once;

(3) K_2,ne, the graph obtained from K_2,n by deleting an edge;

(4) K_2,n⁺, the graph obtained from K_2,n by adding an edge between the two degree-n vertices x₁ and x₂, and a pendent edge at each x_i.

Two applications of this result are also discussed in the paper.     

Homogenization of Elliptic Problems with Neumann Boundary Conditions in Non-smooth Domains

We consider a family of second-order elliptic operators {L_ε} in divergence form with rapidly oscillating and periodic coefficients in Lipschitz and convex domains in R~n. We are able to show that the uniform W~(1,p) estimate of second order elliptic systems holds for 2n/(n+1)-δ p 2n/(n-1)+ δ where δ 0 is independent of ε and the ranges are sharp for n = 2, 3. And for elliptic equations in Lipschitz domains, the W~(1,p) estimate is true for 3/2-δ p 3 + δ if n ≥ 4, similar estimate was extended to convex domains for 1 p ∞.     

Almost perfect matchings in random uniform hypergraphs

We consider the following model H_r(n, p) of random r-uniform hypergraphs. The vertex set consists of two disjoint subsets V of size | V | = n and U of size | U | = (r − 1)n. Each r-subset of V × (_r−1^U) is chosen to be an edge of H ε H_r(n, p) with probability p = p(n), all choices being independent. It is shown that for every 0 < < 1 if P = (C ln n)/n^r−1 with C = C() sufficiently large, then almost surely every subset V₁ V of size | V₁ | = (1 − )n is matchable, that is, there exists a matching M in H such that every vertex of V₁ is contained in some edge of M.     

On parallel rectilinear obstacle- avoiding paths

We give improved space and processor complexities for the problem of computing, in parallel, a data structure that supports queries about shortest rectilinear obstacle-avoiding paths in the plane, where the obstacles are disjoint rectangles. That is, a query specifies any source and destination in the plane, and the data structure enables efficient processing of the query. We now can build the data structure with O(n²/log n) CREW PRAM processors, as opposed to the previous O(n²), and with O(n²) space, as opposed to the previous O(n²(log n)²). The time complexity remains unchanged, at O((log n)²). As before, the data structure we compute enables a query to be processed in O(log n) time, by one processor for obtaining a path length, or by O(k/log n) processors for retrieving a shortest path itself, where k is the number of segments on that path. The new ideas that made our improvement possible include a new partitioning scheme of the recursion tree, which is used to schedule the computations performed on that tree. Since a number of other related shortest paths problems are solved using this technique as a subroutine our improvement translates into a similar improvement in the complexities of these problems as well.     

Existence of three HMOLS of types h and 23

In this paper, we construct 23 new 3 HMOLS of type hⁿ. We also investigate the existence of 3 HMOLS of type 2ⁿ3¹ and show that the necessary condition n 6 is sufficient for such designs to exist except possibly for 18 values of n, of which n = 31 is the largest. As an application, some improvements for the existence of perfect Mendelsohn designs with block size five are also mentioned.     

The growth of laguerre matrix polynomials on bounded intervals

Let A be a matrix in ^r×r such that Re(z) > −1/2 for all the eigenvalues of A and let {π_n^(A,1/2) (x)} be the normalized sequence of Laguerre matrix polynomials associated with A. In this paper, it is proved that π_n^(A,1/2) (x) = O(n^(A)/2ln^r−1(n)) and π_n+1^(A,1/2) (x) − π_n^(A,1/2) (x) = O(n^((A)−1)/2ln^r−1(n)) uniformly on bounded intervals, where (A) = max{Re(z); z eigenvalue of A}.