Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

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.     

R~3中的一个Heilbronn型问题

本文给出Ｈｅｉｌｂｒｏｎｎ型问题的结果．设Ｓ是Ｒ~３中六点组成的集合．直径为Ｄ．若ｄ表示Ｓ中任意两点距离的最小值,则Ｄ≥２ｄ．等号当且仅当Ｓ是由正八面体的六个顶点或多面体面△×△１的六个顶点组成时才成立（△１,△２分别表示一维、二维正则单形,且其棱长相等）．     

The convex dimension of a graph

The convex dimension of a graph G=(V,E) is the smallest dimension d for which G admits an injective map f:V?R^d of its vertices into d-space, such that the barycenters of the images of the edges of G are in convex position. The strong convex dimension of G is the smallest d for which G admits a map as above such that the images of the vertices of G are also in convex position. In this paper we study the convex and strong convex dimensions of graphs.     

On a conformal invariant of the dirac operator on noncompact manifolds

We extend a Yamabe-type invariant of the Dirac operator to noncompact manifolds and show that as in the compact case this invariant is bounded by the corresponding invariant of the standard sphere. Further, this invariant will lead to an obstruction of the conformal compactification of complete noncompact manifolds. Mathematics subject classifications (2000): Primary 53C27, Secondary 53C21     

Nonlinear Filtering Equation of a Jump Process with Counting Observations

We study the filtering problem of an R ^d -valued pure jump process when the observations is a counting process. We assume that the dynamic of the state and the observations may be strongly dependent and that the two processes may jump together. Weak and pathwise uniqueness of solution of the Kushner–Stratonovich equation are discussed.     

The diameter of a fuzzy set

In pattern recognition one often wants to measure geometric properties of imprecisely defined subsets of an image. This paper proposes definitions of intrinsic and extrinsic diameter for fuzzy subsets which reduce to the ordinary definitions when the subsets are crisp. We also define height and width for a fuzzy subset and show how they relate to the area (i.e., integral of membership). For convex fuzzy subsets the intrinsic diameter cannot exceed the extrinsic diameter, but it can be smaller. Finally, for piecewise constant convex fuzzy subsets the intrinsic diameter cannot exceed half the fuzzy perimeter, but this need not be true in the nonconvex case.     

Modelling a Multitype Branching Brownian Motion: Filtering of a Measure-Valued Process

In the framework of marked trees, a multitype branching brownian motion, described by measure-valued processes, is studied. By applying the strong branching property, the Markov property and the expression of the generator are derived for the process whose components are the measure-valued processes associated to each type particles. The conditional law of the measure-valued process describing the whole population observing the cardinality of the subpopulation of a given type particles is characterized as the unique weak solution of the Kushner‐Stratonovich equation. An explicit representation of the filter is obtained by Feyman–Kac formula using the linearized filtering equation.     

A linear-time algorithm for classifying the states of a finite Markov chain

Classifying the states of a finite Markov chain requires the identification of all irreducible closed sets and the set of transient states. This paper presents an algorithm for identifying these states that executes in time O(MAX(|V|, |E|)) where number of states and |E| is the number of positive entries in the Markov matrix. The algorithm finds the closed strongly connected components of the transition graph using a depth-first search.     

Coloring copoints of a planar point set

To a set of n points in the plane, one can associate a graph that has less than n² vertices and has the property that k-cliques in the graph correspond vertex sets of convex k-gons in the point set. We prove an upper bound of 2^k-1 on the size of a planar point set for which the graph has chromatic number k, matching the bound conjectured by Szekeres for the clique number. Constructions of Erd?s and Szekeres are shown to yield graphs that have very low chromatic number. The constructions are carried out in the context of pseudoline arrangements.     

A Slow Transient Diffusion in a Drifted Stable Potential

We consider a diffusion process X in a random potential of the form , where is a positive drift and is a strictly stable process of index with positive jumps. Then the diffusion is transient and converges in law towards an exponential distribution. This behaviour contrasts with the case where is a drifted Brownian motion and provides an example of a transient diffusion in a random potential which is as “slow” as in the recurrent setting.      

The sharp lower bound for the first positive eigenvalue of a sub-Laplacian on a pseudo-Hermitian manifold

This paper studies, using the Bochner technique, a sharp lower bound of the first eigenvalue of a subelliptic Laplace operator on a strongly pseudoconvex CR manifold in terms of its pseudo-Hermitian geometry. For dimensions greater than or equal to , the lower bound under a condition on the Ricci curvature and the torsion was obtained by Greenleaf. We give a proof for all dimensions greater than or equal to . For dimension , the sharp lower bound is proved under a condition which also involves a distinguished covariant derivative of the torsion.

     

A note on maximally repeated sub-patterns of a point set

We answer a question raised by Brass on the number of maximally repeated sub-patterns in a set of n points in R^d. We show that this number, which was conjectured to be polynomial, is in fact Θ(2^n/2) in the worst case, regardless of the dimension d.     

On empty convex polygons in a planar point set

Let P be a set of n points in general position in the plane. Let X_k(P) denote the number of empty convex k-gons determined by P. We derive, using elementary proof techniques, several equalities and inequalities involving the quantities X_k(P) and several related quantities. Most of these equalities and inequalities are new, except for a few that have been proved earlier using a considerably more complex machinery from matroid and polytope theory, and algebraic topology. Some of these relationships are also extended to higher dimensions. We present several implications of these relationships, and discuss their connection with several long-standing open problems, the most notorious of which is the existence of an empty convex hexagon in any point set with sufficiently many points.     

On the points realizing the distance to a definable set

We prove a definable/subanalytic version of a useful lemma, presumably due to John Nash, concerning the points realizing the Euclidean distance to an analytic submanifold of Rn. We present a parameter version of the main result and we discuss the properties of the multifunction obtained.