Obstacle Numbers of Graphs

An obstacle representation of a graph G is a drawing of G in the plane with straight-line edges, together with a set of polygons (respectively, convex polygons) called obstacles, such that an edge exists in G if and only if it does not intersect an obstacle. The obstacle number (convex obstacle number) of G is the smallest number of obstacles (convex obstacles) in any obstacle representation of G. In this paper, we identify families of graphs with obstacle number 1 and construct graphs with arbitrarily large obstacle number (convex obstacle number). We prove that a graph has an obstacle representation with a single convex k-gon if and only if it is a circular arc graph with clique covering number at most k in which no two arcs cover the host circle. We also prove independently that a graph has an obstacle representation with a single segment obstacle if and only if it is the complement of an interval bigraph.     

Steiner minimal trees for three points with one convex polygonal obstacle

The problem of constructing Steiner minimal trees in the Euclidean plane is NP-hard. When in addition obstacles are present, difficulties of constructing obstacle-avoiding Steiner minimal trees are compounded. This problem, which has many obvious practical applications when designing complex transportation and distribution systems, has received very little attention in the literature. The construction of Steiner minimal trees for three terminal points in the Euclidean plane (without obstacles) has been completely solved (among others by Fermat, Torricelli, Cavallieri, Simpson, Heinen) during the span of the last three centuries. This construction is a cornerstone for both exact algorithms and heuristics for the Euclidean Steiner tree problem with arbitrarily many terminal points. An algorithm for three terminal points in the presence of one polygonal convex obstacle is given. It is shown that this algorithm has the worst-case time complexityO(n), wheren is the number of extreme points on the obstacle. As an extension to the underlying algorithm, if the obstacle is appropriately preprocessed inO(n) time, we can solve any problem instance with three arbitrary terminal points and the preprocessed convex polygonal obstacle inO(logn) time. We believe that the three terminal points algorithm will play a critical role in the development of heuristics for problem instances with arbitrarily many terminal points and obstacles.     

Rigidity of generalized laplacians and some geometric applications

Summary Every generalized laplacianL defined on a manifoldM determines a sheaf of L-harmonic sections namely the sheaf of local solutions ofLu = 0. We study the converse problem: to what extent this sheaf determines the operator. Our main result states that the sheaf ofL-harmonic sections determines the operator up to a conformal factor. Moreover, when the operator is a covariant laplacian and the dimension ofM is greater than 2, the sheaf determinesL up to a multiplicative constant. An interesting consequence is the following: if two Riemann metrics on a smooth manifold of dimension greater than 2 have the same sheaves of harmonic functions then they are homothetic.     

A topological minorization for the volume of vector fields on 5-manifolds

A vector field X on a Riemannian manifold determines a submanifold in the tangent bundle. The volume of X is the volume of this submanifold for the induced Sasaki metric. When M is compact, the volume is well defined and, usually, this functional is studied for unit fields. Parallel vector fields are trivial minima of this functional.For manifolds of dimension 5, we obtain an explicit result showing how the topology of a vector field with constant length influences its volume. We apply this result to the case of vector fields that define Riemannian foliations with all leaves compact.Received: 29 April 2004     

On the Structure of Graphs with Low Obstacle Number

The obstacle number of a graph G is the smallest number of polygonal obstacles in the plane with the property that the vertices of G can be represented by distinct points such that two of them see each other if and only if the corresponding vertices are joined by an edge. We list three small graphs that require more than one obstacle. Using extremal graph theoretic tools developed by Pr?mel, Steger, Bollobás, Thomason, and others, we deduce that for any fixed integer h, the total number of graphs on n vertices with obstacle number at most h is at most 2^o(n2){2^{o(n^2)}}. This implies that there are bipartite graphs with arbitrarily large obstacle number, which answers a question of Alpert et al. (Discret Comput Geom doi:, 2009).     

Inverse Problems for Obstacles in a Waveguide

In this paper we prove that a particular entry in the scattering matrix, if known for all energies, determines certain rotationally symmetric obstacles in a generalized waveguide. The generalized waveguide X can be of any dimension and we allow either Dirichlet or Neumann boundary conditions on the boundary of the obstacle and on ?X. In the case of a two-dimensional waveguide, two particular entries of the scattering matrix suffice to determine the obstacle, without the requirement of symmetry.     

The Number of Cyclic Configurations of Type (v3) and the Isomorphism Problem

A configuration of points and lines is cyclic if it has an automorphism that permutes its points in a full cycle. A closed formula is derived for the number of nonisomorphic connected cyclic configurations of type (v₃), i.e. which have v points and lines, and each point/line is incident with exactly three lines/points. In addition, a Bays–Lambossy type theorem is proved for cyclic configurations if the number of points is a product of two primes or a prime power.     

Planar rectilinear shortest path computation using corridors

The rectilinear shortest path problem can be stated as follows: given a set of m non-intersecting simple polygonal obstacles in the plane, find a shortest L₁-metric (rectilinear) path from a point s to a point t that avoids all the obstacles. The path can touch an obstacle but does not cross it. This paper presents an algorithm with time complexity O(n+m(lgn)^3/2), which is close to the known lower bound of Ω(n+mlgm) for finding such a path. Here, n is the number of vertices of all the obstacles together.     

Efficiently updating constrained Delaunay triangulations

TheConstrained Delaunay Triangulation of a set of obstacle line segments in the plane is the Delaunay triangulation of the endpoint set of these obstacles with the restriction that the edge set of the triangulation contains all these obstacles. In this paper we present an optimal (logn +k) algorithm for inserting an obstacle line segment or deleting an obstacle edge in the constrained Delaunay triangulation of a set ofn obstacle line segments in the plane. Herek is the number of Delaunay edges deleted and added in the triangulation during the updates.This work is supported by NSERC grant OPG0041629.     

Planar central configurations as fixed points

Planar central configurations can be seen as critical points of the reduced potential or solutions of a system of equations. By the homogeneity of the potential and its O(2)-invariance it is possible to see that the SO(2)- orbits of central configurations are fixed points of a map f. The purpose of the paper is to define and study this map and to derive some properties using topological fixed point theory. The generalized Moulton–Smale theorem for collinear configurations is proved, together with some estimates on the number of central configurations in the case of three bodies, using fixed point indices. Well-known results such as the compactness of the set of central configurations follow easily in this topological framework. Dedicated to Professor Albrecht Dold and Professor Edward Fadell     

Confinement of Brownian motion among Poissonian obstacles in ℝ d , d≥ 3

Consider Brownian motion among random obstacles obtained by translating a fixed compact nonpolar subset of ℝ ^d , d≥ 1, at the points of a Poisson cloud of constant intensity v <: 0. Assume that Brownian motion is absorbed instantaneously upon entering the obstacle set. In SZN-conf Sznitman has shown that in d = 2, conditionally on the event that the process does not enter the obstacle set up to time t, the probability that Brownian motion remains within distance ∼t ^1/4 from its starting point is going to 1 as t goes to infinity. We show that the same result holds true for d≥ 3, with t ^1/4 replaced by t ^{1/( d +2)}. The proof is based on Sznitmans refined method of enlargement of obstacles [10] as well as on a quantitative isoperimetric inequality due to Hall [4]. Received: 6 July 1998     

On Lundh’s percolation diffusion

A collection of spherical obstacles in the unit ball in Euclidean space is said to be avoidable for Brownian motion if there is a positive probability that Brownian motion diffusing from some point in the ball will avoid all the obstacles and reach the boundary of the ball. The centres of the spherical obstacles are generated according to a Poisson point process while the radius of an obstacle is a deterministic function. If avoidable configurations are generated with positive probability, Lundh calls this percolation diffusion. An integral condition for percolation diffusion is derived in terms of the intensity of the point process and the function that determines the radii of the obstacles.     

The Brake Orbits of Hamiltonian Systems on Positive-type Hypersurfaces

This paper deals with the brake orbits of Hamiltonian system on given energy hypersurfaces Σ = H ⁻¹(1). We introduce a class of contact type but not necessarily star-shaped hypersurfaces in ℝ²ⁿ and call them normalized positive-type hypersurfaces. By using of the critical point theory, we prove that if Σ is a partially symmetric normalized positive-type hypersurface, it must carries a brake orbit of (HS). Furthermore, we obtain some multiplicity results under certain pinching conditions. Our results include the earlier works on this subject given by P. Rabinowitz and A. Szulkin in star-shaped case. An example of partially symmetric normalized positive-type hypersurface in ℝ⁴ that is not star-shaped is also presented Partially supported by NNSF of China (10571085) and Science Foundation of Hohai University.     

Critical points of the total scalar curvature functional on the space of metrics of constant scalar curvature

It is well known that critical points of the total scalar curvature functional ? on the space of all smooth Riemannian structures of volume 1 on a compact manifold M are exactly the Einstein metrics. When the domain of ? is restricted to the space of constant scalar curvature metrics, there has been a conjecture that a critical point is also Einstein or isometric to a standard sphere. In this paper we prove that n-dimensional critical points have vanishing n− 1 homology under a lower Ricci curvature bound for dimension less than 8. Received: 12 July 1999     

A GEOMETRIC SPLITTING AND THE C∞ STABILITY OF MAPS FROM SEMIANALYTIC SETS

Abstract

John Mather has proved that infinitesimal stability implies stability for proper maps in the category of smooth manifolds. This result gives a computable algebraic criterion for stability. In this paper it is shown that there is an extension of Mather's result when the range is only assumed to be a compact semianalytic set of some real Euclidean space—this class of spaces is an obvious maximal candidate for which computations can be carried out using only classical polynomial algebra. The proof depends on a splitting theorem for the restriction map from the smooth functions on a Euclidean space to those on a closed subset and is proved by an algebraic-geometric method derived from the work of B. Malgrange. No knowledge of functional analysis is assumed although an alternative analytic method for proving the main result is also indicated. Only simple applications are given (mostly to functions defined locally in the neighbourhood of an isolated hypersurface singularity of the type studied by J. Milnor and others) since the author intends to publish a fairly comprehensive study of stability (smooth and C°) of smooth maps on closed semianalytic sets.     

Hazard and safety regions for paths with constrained curvature

In this paper the problem of collision analysis for a mobile robot operating in a planar environment with moving objects (obstacles) is addressed. The pattern of motion of the potential obstacles cannot be predicted; only a bound on their maximum velocity is available. Based on this information, at its current position the robot constructs the Hazard Region that corresponds to the path it contemplates. If the Hazard Region contains at least one obstacle, then there is a potential for this obstacle to collide with the robot (in which case perhaps another path should be planned). We first derive the solution for Hazard Region for two standard path primitives, a straight line segment and a circular arc segment; the solution is exact, except for one special case (for which the approximation error is estimated). This result is then applied to a more complex case when the path presents a combination of those primitives. Such are, for example, the optimal (shortest) paths with constrained curvature (known as Dubins paths [3]), which connect two points, each with a prescribed direction of motion. © 1998 B. G. Teubner Stuttgart—John Wiley & Sons, Ltd.     

Motion Planning in Environments with Low Obstacle Density

We present a simple and efficient paradigm for computing the exact solution of the motion planning problem in environments with a low obstacle density. Such environments frequently occur in practical instances of the motion planning problem. The complexity of the free space for such environments is known to be linear in the number of obstacles. Our paradigm is a new cell decomposition approach to motion planning and exploits properties that follow from the low density of the obstacles in the robot's workspace. These properties allow us to decompose the workspace, subject to some constraints, rather than to decompose the higher-dimensional free configuration space directly. A sequence of uniform steps transforms the workspace decomposition into a free space decomposition of asymptotically the same size. The approach leads to nearly optimal O(n \log n) motion planning algorithms for free-flying robots with any fixed number of degrees of freedom in workspaces with low obstacle density. Received October 17, 1995, and in revised form July 8, 1997, and February 23, 1998.     

Stochastic flows on the boundaries of SL(n,R)

Summary We study the asymptotic stability of the stochastic flows on a class of compact spaces induced by a diffusion process in SL(n, R) or GL(n, R). These compact spaces are called boundaries of SL(n, R), which include SO(n), the flag manifold, the sphereS ⁿ–1 and the Grassmannians. The one point motions of these flows are Brownian motions. For almost every, , we determine the set of stable points. This is a random open set whose complement has zero Lebesgue measure. The distance between any two points in the same component of this set tends to zero exponentially fast under the flow. The Lyapunov exponents at stable points are computed explicitly. We apply our results to a stochastic flow onS ⁿ–2 generated by a stochastic differential equation which exhibits some nice symmetry.Research supported in part by Hou Yin Dong Education Foundation of China On leave from Nankai University, Tianjin, China     

Renormalization and conjugacy of piecewise linear Lorenz maps

We investigate the uniform piecewise linearizing question for a family of Lorenz maps. Let f be a piecewise linear Lorenz map with different slopes and positive topological entropy, we show that f is conjugate to a linear mod one transformation and the conjugacy admits a dichotomy: it is either bi-Lipschitz or singular depending on whether f is renormalizable or not. f is renormalizable if and only if its rotation interval degenerates to be a rational point. Furthermore, if the endpoints are periodic points with the same rotation number, then the conjugacy is quasisymmetric.     

An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space

We present an efficient algorithm for planning the motion of a convex polygonal bodyB in two-dimensional space bounded by a collection of polygonal obstacles. Our algorithm extends and combines the techniques of Leven and Sharir and of Sifrony and Sharir used for the case in whichB is a line segment (a ladder). It also makes use of the results of Kedem and Sharir on the planning of translational motion ofB amidst polygonal obstacles, and of a recent result of Leven and Sharir on the number of free critical contacts ofB with such polygonal obstacles. The algorithm runs in timeO(kn ₆(kn) logkn), wherek is the number of sides ofB, n is the number of obstacle edges, and ,(q) is an almost linear function ofq yielding the maximal number of connected portions ofq continuous functions which compose the graph of their lower envelope, where it is assumed that each pair of these functions intersect in at mosts points.Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.