Improved Approximation Algorithms for Geometric Set Cover

Given a collection S of subsets of some set and the set cover problem is to find the smallest subcollection that covers that is, where denotes We assume of course that S covers While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where usually Combining previously known techniques [4], [5], we show that polynomial-time approximation algorithms with provable performance exist, under a certain general condition: that for a random subset and nondecreasing function f(·), there is a decomposition of the complement into an expected at most f(|R|) regions, each region of a particular simple form. Under this condition, a cover of size O(f(|C|)) can be found in polynomial time. Using this result, and combinatorial geometry results implying bounding functions f(c) that are nearly linear, we obtain o(log c) approximation algorithms for covering by fat triangles, by pseudo-disks, by a family of fat objects, and others. Similarly, constant-factor approximations follow for similar-sized fat triangles and fat objects, and for fat wedges. With more work, we obtain constant-factor approximation algorithms for covering by unit cubes in and for guarding an x-monotone polygonal chain.     

Maximum Hitting of a Set by Compressed Intersecting Families

For a family A{\mathcal{A}} and a set Z, denote {A ? A \colon A ?Z 1 ?}{\{A \in \mathcal{A} \colon A \cap Z \neq \emptyset\}} by A(Z){\mathcal{A}(Z)}. For positive integers n and r, let S_n,r{\mathcal{S}_{n,r}} be the trivial compressed intersecting family {A ? (c[n]r ) \colon 1 ? A}{\{A \in \big(\begin{subarray}{c}[n]\\r \end{subarray}\big) \colon 1 \in A\}}, where [n] : = {1, ?, n}{[n] := \{1, \ldots, n\}} and (c[n]r ) : = {A ì [n] \colon |A| = r}{\big(\begin{subarray}{c}[n]\\r \end{subarray}\big) := \{A \subset [n] \colon |A| = r\}}. The following problem is considered: For r ≤ n/2, which sets Z í [n]{Z \subseteq [n]} have the property that |A(Z)| ￡ |S_n,r(Z)|{|\mathcal{A}(Z)| \leq |\mathcal{S}_{n,r}(Z)|} for any compressed intersecting family A ì (c[n]r ){\mathcal{A}\subset \big(\begin{subarray}{c}[n]\\r \end{subarray}\big)}? (The answer for the case 1 ? Z{1 \in Z} is given by the Erdős–Ko–Rado Theorem.) We give a complete answer for the case |Z| ≥ r and a partial answer for the much harder case |Z| < r. This paper is motivated by the observation that certain interesting results in extremal set theory can be proved by answering the question above for particular sets Z. Using our result for the special case when Z is the r-segment {2, ?, r+1}{\{2, \ldots, r+1\}}, we obtain new short proofs of two well-known Hilton–Milner theorems. At the other extreme end, by establishing that |A(Z)| ￡ |S_n,r(Z)|{|\mathcal{A}(Z)| \leq |\mathcal{S}_{n,r}(Z)|} when Z is a final segment, we provide a new short proof of a Holroyd–Talbot extension of the Erdős-Ko-Rado Theorem.     

A Note on Hitting Maximum and Maximal Cliques With a Stable Set

It was recently proved that any graph satisfying contains a stable set hitting every maximum clique. In this note, we prove that the same is true for graphs satisfying unless the graph is the strong product of an odd hole and .We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.     

Two Unsolved Geometric Problems

Two familiar unsolved geometric problems are discussed: on functions on the 2-sphere and on quadrangles inscribed in a smooth planar Jordan curve. A related question on equipartitioning a mass on a plane is also discussed. Bibliography: 6 titles.     

Notes on Two Geometric Inequalities for a Finite Set of Points

Two geometric inequalities for a finite set of points were established in Geom. Dedicata 62 (1996), 157--160. In this paper, we point out a computational mistake in that paper, and give corrections to two geometric inequalities.     

几何直观在特征值问题中的应用

借助MATLAB软件将几何直观方法应用于矩阵特征向量的判定、二次曲线的绘制、二次型的分类和微分方程组动力学性质刻画等线性代数特征值问题教学之中,以实例说明几何直观在线性代数课程教学中的应用.     

Extremal Problems for Geometric Hypergraphs

A geometric hypergraph H is a collection of i -dimensional simplices, called hyperedges or, simply, edges, induced by some (i+1) -tuples of a vertex set V in general position in d -space. The topological structure of geometric graphs, i.e., the case d=2 , i=1 , has been studied extensively, and it proved to be instrumental for the solution of a wide range of problems in combinatorial and computational geometry. They include the k -set problem, proximity questions, bounding the number of incidences between points and lines, designing various efficient graph drawing algorithms, etc. In this paper, we make an attempt to generalize some of these tools to higher dimensions. We will mainly consider extremal problems of the following type. What is the largest number of edges (i -simplices) that a geometric hypergraph of n vertices can have without containing certain forbidden configurations? In particular, we discuss the special cases when the forbidden configurations are k intersecting edges, k pairwise intersecting edges, k crossing edges, k pairwise crossing edges, k edges that can be stabbed by an i -flat, etc. Some of our estimates are tight. Received March 4, 1996, and in revised form September 13, 1996.     

Ramsey-Type Results for Geometric Graphs, II

We show that for any two-coloring of the segments determined by n points in the plane, one of the color classes contains noncrossing cycles of lengths . This result is tight up to a multiplicative constant. Under the same assumptions, we also prove that there is a noncrossing path of length Ω(n ^2/3 ) , all of whose edges are of the same color. In the special case when the n points are in convex position, we find longer monochromatic noncrossing paths, of length . This bound cannot be improved. We also discuss some related problems and generalizations. In particular, we give sharp estimates for the largest number of disjoint monochromatic triangles that can always be selected from our segments. Received March 25, 1997, and in revised form March 5, 1998.     

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.     

Some Problems of Local Hitting, Scaling, and Conditioning

The aim of this paper is to convey the basic ideas regarding some local hitting and conditioning properties of random measures. Some very general results are obtainable in the special case of simple point processes. Though much of this theory has no counterpart for general random measures, similar results do exist in two cases of special interest—for local time random measures and for Dawson–Watanabe superprocesses. This is an informal account of some of the basic hitting and conditioning properties common to all three cases. Precise statements and proofs will be provided elsewhere.     

有关拓扑学与覆盖粗糙集的一些结论

引入了拓扑覆盖的概念,并结合最小描述元对有限论域上的拓扑覆盖加于研究,得出了拓扑覆盖的最简覆盖和基与最小描述元之间的关系.介绍了在基于有限论域U上的覆盖,构造U上的一个拓扑的方法.并且在最小描述元的基础上将划分下的粗糙隶属函数推广至一般覆盖下的粗糙隶属函数,而后介绍了其相关运用.     

Lipschitz Regularity in Some Geometric Problems

The Lipschitz regularity is perhaps the most natural, and surely the most geometrical among all the types of regularities. For example, the Lipschitz character of an ordinary differential equation (vector field) is the natural classical sufficient condition for the (unique) integrability of this equation. The goal here is to show that, in some sense, the Lipschitz regularity is also necessary, if one assumes (geometric) individual conditions on the trajectories. In other words, we show that tangential rigidity leads to a transversal regularity.     

Second-Order Optimality Conditions and Improved Convergence Results for Regularization Methods for Cardinality-Constrained Optimization Problems

We consider nonlinear optimization problems with cardinality constraints. Based on a continuous reformulation, we introduce second-order necessary and sufficient optimality conditions. Under such a second-order condition, we can guarantee local uniqueness of Mordukhovich stationary points. Finally, we use this observation to provide extended local convergence theory for a Scholtes-type regularization method, which guarantees the existence and convergence of iterates under suitable assumptions. This convergence theory can also be applied to other regularization schemes.     

Results on Nonlocal Boundary Value Problems

In this article, we provide a variational theory for nonlocal problems where nonlocality arises due to the interaction in a given horizon. With this theory, we prove well-posedness results for the weak formulation of nonlocal boundary value problems with Dirichlet, Neumann, and mixed boundary conditions for a class of kernel functions. The motivating application for nonlocal boundary value problems is the scalar stationary peridynamics equation of motion. The well-posedness results support practical kernel functions used in the peridynamics setting.

We also prove a spectral equivalence estimate which leads to a mesh size independent upper bound for the condition number of an underlying discretized operator. This is a fundamental conditioning result that would guide preconditioner construction for nonlocal problems. The estimate is a consequence of a nonlocal Poincaré-type inequality that reveals a horizon size quantification. We provide an example that establishes the sharpness of the upper bound in the spectral equivalence.     

Some Results on Secant Varieties Leading to a Geometric Flip Construction

We study the relationship between the equations defining a projective variety and properties of its secant varieties. In particular, we use information about the syzygies among the defining equations to derive smoothness and normality statements about SecX and also to obtain information about linear systems on the blow up of projective space along a variety X. We use these results to geometrically construct, for varieties of arbitrary dimension, a flip first described in the case of curves by M. Thaddeus via Geometric Invariant Theory.     

几何规划问题的一种分枝定界方法

本文通过指数函数变换，把解几何规划GP（Ω）等价地转化为另外一个非线优化问题NLP（－↑Ω），根据问题（－↑Ω）的结构特征，构造它的一个线性规划松驰上确定它的最优值的一个下界，由此给出问题GP（Ω）的一个新的分枝定界算法。最后证明了这个算法是收敛的。