Tight Bounds for Connecting Sites Across Barriers

Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight line minimum cost spanning tree on the sites, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines, it is known that there is a spanning tree such that every barrier is crossed by tree edges, and this bound is asymptotically optimal. Asano et al. showed that if the barriers are pairwise disjoint line segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Lower bound constructions are known with 3 crossings per barrier and 2n total cost. We obtain tight bounds on the minimum cost of spanning trees in the special case where the barriers are interior disjoint line segments that form a convex subdivision of the plane and there is a point in every cell of the subdivision. In particular, we show that there is a spanning tree such that every barrier crosses at most 2 tree edges, and there is a spanning tree of total cost 5n/3. Both bounds are the best possible. Work by Eynat Rafalin and Diane Souvaine was supported by the National Science Foundation under Grant #CCF-0431027. E. Rafalin’s research conducted while at Tufts University.     

Illuminating Disjoint Line Segments in the Plane

It is shown that a set of $n$ disjoint line segments in the plane can always be illuminated by $\lfloor (n+1)/2\rfloor$ light sources, improving an earlier bound of $\lfloor 2n/3\rfloor$ due to Czyzowicz et al. It is also shown that $\lfloor 4(n+1)/5 \rfloor$ light sources are always sufficient and sometimes necessary to illuminate the free space and both sides of $n$ disjoint line segments for every $n\geq 2$.     

Every Set of Disjoint Line Segments Admits a Binary Tree

Given a set of n disjoint line segments in the plane, we show that it is always possible to form a tree with the endpoints of the segments such that each line segment is an edge of the tree, the tree has no crossing edges, and the maximum vertex degree of the tree is 3. Furthermore, there exist configurations of line segments where any such tree requires degree 3. We provide an O(nlog n) time algorithm for constructing such a tree, and show that this is optimal. Received September 14, 1999, and in revised form January 17, 2001. Online publication August 29, 2001.     

Extrapolation of Nyström Solutions of Boundary Integral Equations on Non-Smooth Domains

The interior Dirichlet problem for Laplace's equation on a plane polygonal region $\Omega$ with boundary $\Gamma$ may be reformulated as a second kind integral equation on $\Gamma$. This equation may be solved by the Nyström method using the composite trapezoidal rule. It is known that if the mesh has $O(n)$ points and is graded appropriately, then $O(1/n^2)$ convergence is obtained for the solution of the integral equation and the associated solution to the Dirichlet problem at any $x\in \Omega$. We present a simple extrapolation scheme which increases these rates of convergence to $O(1/n^4)$ .     

Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles

We provide a variety of new upper and lower bounds and simpler proof techniques for the efficient construction of binary space partitions (BSPs) of axis-parallel rectangles of various dimensions. (a) We construct a set of $n$ disjoint axis-parallel segments in the plane such that any binary space auto-partition has size at least $2n-o(n)$, almost matching an upper bound of dAmore and Franciosa. (b) We establish a similar lower bound of $7n/3-o(n)$ for disjoint rectangles in the plane. (c) We simplify and improve BSP constructions of Paterson and Yao for disjoint segments in $\reals^d$ and disjoint rectangles in $\reals^3$. (d) We derive a worst-case bound of $\Theta(n^{5/3})$ for the size of BSPs of disjoint $2$-rectangles in $4$-space. (e) For disjoint $k$-rectangles in $d$-space, we prove the worst-case bound $\Theta(n^{d/(d-k)})$, for any $k<d/2$; this bound holds for all $k<d$ if the rectangles are allowed to intersect.     

几乎无爪图的叶子数较少的生成树

A spanning tree with no more than 3 leaves is called a spanning 3-ended tree.In this paper, we prove that if G is a k-connected(k ≥ 2) almost claw-free graph of order n and σ_(k+3)(G) ≥ n + k + 2, then G contains a spanning 3-ended tree, where σk(G) =min{∑_(v∈S)deg(v) : S is an independent set of G with |S| = k}.     

Cuttings for Disks and Axis-Aligned Rectangles in Three-Space

We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r∈?, a $\frac{1}{r}We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r∈ℕ, a \frac1r\frac{1}{r} -cutting is a covering of the space with simplices such that the interior of each simplex intersects at most n/r objects. For n pairwise disjoint disks in ℝ³ and a parameter r∈ℕ, we construct a \frac1r\frac{1}{r} -cutting of size O(r ²). For n axis-aligned rectangles in ℝ³, we construct a \frac1r\frac{1}{r} -cutting of size O(r ^3/2). As an application related to multi-point location in three-space, we present tight bounds on the cost of spanning trees across barriers. Given n points and a finite set of disjoint disk barriers in ℝ³, the points can be connected with a straight line spanning tree such that every disk is stabbed by at most O(?n)O(\sqrt{n}) edges of the tree. If the barriers are axis-aligned rectangles, then there is a straight line spanning tree such that every rectangle is stabbed by O(n ^1/3) edges. Both bounds are best possible.     

Fast Parallel Algorithms for Computing Generalized Inverses $A^+$ and $A_{MN}^+$

The parallel arithmetic complexities for computing generalized inverse $A^+$, computing the minimum-norm least-squares solution of $Ax=b$, computing order $m+n-r$ determinants and finding the characteristic polynomials of order $m+n-r$ matrices are shown to have the same grawth rate. Algorithms are given that compute $A^+$ and $A_{MN}^+$ in $O(\log r\dot \log n+\log m)$ and $O(\log^2n+\log m)$ steps using a number of processors which is a polynomial in $m, \ n$ and $r$ $(A\in B_r^{m\times n},r=rank \ A)$.     

On the Complexity of Halfspace Area Queries

Given a nonconvex simple polygon $P$ with $n$ vertices, is it possible to construct a data structure which after preprocessing can answer halfspace area queries (i.e., given a line, determine the area of the portion of the polygon above the line) in $o(n)$ time? We answer negatively, proving an $\Omega(n)$ lower bound on the query time of any data structure performing this task. We then consider the offline version of the same problem: given a polygon $P$ with $n$ vertices, and $k$ query lines, we present an algorithm that computes the area of $P$ on both sides of each line in $O(k^{2/3}n^{2/3+\varepsilon}+(n+k)\polylog{n})$ time. Variants of this method allow the query of a collection of weighted polygons with or without holes, and solve several other related problems within the same time bounds.     

Error Estimates for the Finite Element Solutions of Some Variational Inequalities with Nonlinear Monotone Operator

In this paper, we estimate the error of the linear finite element solutions of the obstacle problem and the unilateral problem with monotone operator. We obtained $O(h)$ error bound for the obstacle problem and $O(h^{3/4})$ error bound for the unilateral problem. And if the solution $u^*$ of the unilateral problem possesses more smoothness, then $O(h)$ error bound can be obtained in the same way as [2].     

Illumination in the presence of opaque line segments in the plane

What is the minimal number of light sources which is always sufficient to illuminate the plane in the presence of n disjoint opaque line segments? For n5, O'Rourke proved that 2n/3 light sources are always sufficient and sometimes necessary, if light sources can be placed on the line segments and thus they can illuminate both sides of a segment.

We prove that 2(n+1)/3 light sources are always sufficient and sometimes necessary, if light sources cannot be placed on the line segments. An O(nlogn) time algorithm is presented which allocates at most 2(n+1)/3 light sources collectively illuminating the plane.     

Minimizing the Stabbing Number of Matchings, Trees, and Triangulations

The (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. This paper deals with finding perfect matchings, spanning trees, or triangulations of minimum stabbing number for a given set of vertices. The complexity of finding a spanning tree of minimum stabbing number is one of the original 30 questions on “The Open Problems Project” list of outstanding problems in computational geometry by Demaine, Mitchell, and O’Rourke. We show -hardness of stabbing problems by means of a general proof technique. For matchings, this also implies a nontrivial lower bound on the approximability. On the positive side, we propose a cut-based integer programming formulation for minimizing the stabbing number of matchings and spanning trees. From the corresponding linear programming relaxation we obtain polynomial-time lower bounds and show that there always is an optimal fractional solution that contains an edge of at least constant weight. We conjecture that the resulting iterated rounding scheme constitutes a constant-factor approximation algorithm. An extended abstract appeared in the Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms [11]. M.E. Lübbecke visits to Kingston and Stony Brook were supported by a DFG travel grant. H. Meijer partially supported by NSERC while visiting Braunschweig in 2002.     

Disjoint Compatible Geometric Matchings

We prove that for every set of n pairwise disjoint line segments in the plane in general position, where n is even, there is another set of n segments such that the 2n segments form pairwise disjoint simple polygons in the plane. This settles in the affirmative the Disjoint Compatible Matching Conjecture by Aichholzer et al. (Comput. Geom. 42:617–626, 2009). The key tool in our proof is a novel subdivision of the free space around n disjoint line segments into at most n+1 convex cells such that the dual graph of the subdivision contains two edge-disjoint spanning trees.     

Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K_2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a₁,…, a_k) is a color distribution for the complete graph K_n, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K_n with the above distribution if T is a non‐star multicolored spanning tree of K_n, then there exists a multicolored spanning tree T' of K_n such that T and T' are edge‐disjoint. Also it is shown that if K_n, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007     

Minimum cost forest games

In this paper we consider a generalization of the minimum cost spanning tree game. The generalized model allows for more than one supplier, where each supplier offers a different type of service to the customers and each customer specifies a non-empty subset of these suppliers to which he wishes to be connected. We show that the core of such a game may be empty, but that it is always non-empty if there is at least one customer who wants to be connected to all suppliers. Furthermore, the core is always non-empty if there are at most two suppliers.     

The skin effect in vibrating systems with many concentrated masses

We address the asymptotic behaviour of the vibrations of a body occupying a domain $\Omega\subset\mathbb{R}^n, n=2,3$. The density, which depends on a small parameter $\varepsilon$\nopagenumbers\end , is of the order $O(1)$\nopagenumbers\end out of certain regions where it is $O(\varepsilon^{‐m})$\nopagenumbers\end with $m>2$\nopagenumbers\end . These regions, the concentrated masses with diameter $O(\varepsilon)$\nopagenumbers\end , are located near the boundary, at mutual distances $O(\eta)$\nopagenumbers\end , with $\eta=\eta(\varepsilon)\rightarrow 0$\nopagenumbers\end . We impose Dirichlet (resp. Neumann) conditions at the points of $\partial\Omega$\nopagenumbers\end in contact with (resp. out of) the masses. We look at the asymptotic behaviour, as $\varepsilon\rightarrow 0$\nopagenumbers\end , of the eigenvalues of order $O(1)$\nopagenumbers\end , the high frequencies, of the corresponding eigenvalue problem. We show that they accumulate on the whole positive real axis and characterize those giving rise to global vibrations of the whole system. We use the fact that the corresponding eigenfunctions, microscopically, present a skin effect in the concentrated masses. Copyright © 2001 John Wiley & Sons, Ltd.     

双圈图的零度与其匹配数之间的关系

Let G be a graph with n(G) vertices and m(G) be its matching number.The nullity of G,denoted by η(G),is the multiplicity of the eigenvalue zero of adjacency matrix of G.It is well known that if G is a tree,then η(G) = n(G)-2m(G).Guo et al.[Jiming GUO,Weigen YAN,Yeongnan YEH.On the nullity and the matching number of unicyclic graphs.Linear Alg.Appl.,2009,431:1293 1301]proved that if G is a unicyclic graph,then η(G)equals n(G)-2m(G)-1,n(G)-2m(G),or n(G)-2m(G) +2.In this paper,we prove that if G is a bicyclic graph,then η(G) equals n(G)-2m(G),n(G)-2m(G)±1,n(G)-2m(G)±2or n(G)-2m(G) + 4.We also give a characterization of these six types of bicyclic graphs corresponding to each nullity.     

不动点集为$P(2m, 2l+1) \sqcup P(2m, 2n+1)$的对合

设$(M,\,T)$是一个带有光滑对合$T$的光滑闭流形, $T$在$M$上的不动点集为 $F=\{x\,|\,T(x)=x,\,x\in M\}$, 则$F$为$M$的闭子流形的不交并. 本文证明了： 当$F=P(2m,\,2l+1)\sqcup P(2m,\,2n+1)$时,其中$n>l\geq m,\,m\neq1,\,3$, $(M,\,T)$协边于零.     

Ramsey-Type Results for Geometric Graphs, I

For any 2-coloring of the segments determined by n points in general position in the plane, at least one of the color classes contains a non-self-intersecting spanning tree. Under the same assumptions, we also prove that there exist pairwise disjoint segments of the same color, and this bound is tight. The above theorems were conjectured by Bialostocki and Dierker. Furthermore, improving an earlier result of Larman et al., we construct a family of m segments in the plane, which has no more than members that are either pairwise disjoint or pairwise crossing. Finally, we discuss some related problems and generalizations. Received October 17, 1995, and in revised form February 10, 1996.     

New Constructions of Weak ε-Nets

A finite set $N \subset \R^d$ is a {\em weak $\eps$-net} for an $n$-point set $X\subset \R^d$ (with respect to convex sets) if $N$ intersects every convex set $K$ with $|K\,\cap\,X|\geq \eps n$. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al., that every point set $X$ in $\R^d$ admits a weak $\eps$-net of cardinality $O(\eps^{-d}\polylog(1/\eps))$. Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak $\eps$-nets in time $O(n\ln(1/\eps))$.