On the intersection of maximalm-convex subsets

A subsetS of a real linear spaceE is said to bem-convex providedm≧2, there exist more thanm points inS, and for eachm distinct points ofS at least one of the ( ₂ ^m ) segments between thesem points is included inS. InE, letxy denote the segment between two pointsx andy. For any pointx inSυE, letS _x ={y: xyυS}. The kernel of a setS is then defined as {xεS: S _x=S}. It is shown that the kernel of a setS is always a subset of the intersection of all maximalm-convex subsets ofS. A sufficient condition is given for the intersection of all the maximalm-convex subsets of a setS to be the kernel ofS.     

Protecting convex sets

A point-setS is protecting a collection F =T ₁,T ₂,..., _n ofn mutually disjoint compact sets if each one of the setsT _i is visible from at least one point inS; thus, for every setT _i ∈F there are points xS andy T _i such that the line segment joining x to y does not intersect any element inF other thanT _i . In this paper we prove that [2(n-2)/3] points are always sufficient and occasionally necessary to protect any family F ofn mutually disjoint compact convex sets. For an isothetic family F, consisting ofn mutually disjoint rectangles, [n/2] points are always sufficient and [n/2] points are sometimes necessary to protect it. IfF is a family of triangles, [4n/7] points are always sufficient. To protect families ofn homothetic triangles, [n/2] points are always sufficient and [n/2] points are sometimes necessary.     

On the limit of multiple packings

For a collection of subsets of a setS, letn _k be the maximal number of sets from such that no point ofS belongs to more thank of them. Then the limitδ of the sequencen _k /k is related to the valuev of the game in which the minimizer selects a setα in , the maximizer a pointx inS, and the payoff is? _α (x), byδ≤v ^?1≤inf _v δ _v . Herev is any finite subset ofS and δ _v the corresponding limit. Analogous results hold for covering. The bounds obtained in this way forn _k and in particularn ₁ reflect the influence of the boundary ofS when, for instance,S is a convex body to be packed with congruent copies of another body. In some cases, the bounds are sharp.     

Separating convex sets in the plane

Given a setA inR ² and a collectionS of plane sets, we say that a lineL separatesA fromS ifA is contained in one of the closed half-planes defined byL, while every set inS is contained in the complementary closed half-plane.We prove that, for any collectionF ofn disjoint disks inR ², there is a lineL that separates a disk inF from a subcollection ofF with at least (n–7)/4 disks. We produce configurationsH _n andG _n , withn and 2n disks, respectively, such that no pair of disks inH _n can be simultaneously separated from any set with more than one disk ofH _n , and no disk inG _n can be separated from any subset ofG _n with more thann disks.We also present a setJ _m with 3m line segments inR ², such that no segment inJ _m can be separated from a subset ofJ _m with more thanm+1 elements. This disproves a conjecture by N. Alonet al. Finally we show that ifF is a set ofn disjoint line segments in the plane such that they can be extended to be disjoint semilines, then there is a lineL that separates one of the segments from at least n/3+1 elements ofF.     

Helly-type theorems for spheres

We prove that (i) a familyF of at leastn+3 spheres inE ⁿ has nonempty intersection if eachn+1 spheres ofF have nonempty intersection, and (ii) if a familyF of spheres inE ⁿ has nonempty intersection, then there existn+1 or fewer spheres inF whose intersection coincides with the intersection of all spheres ofF.Dedicated to Professor Itiro Tamura on his 60th birthday     

Characterizing compact unions of two starshaped sets inR d

SetS inR ^d has propertyK ₂ if and only ifS is a finite union ofd-polytopes and for every finite setF in bdryS there exist points c₁,c₂ (depending onF) such that each point ofF is clearly visible viaS from at least one c_i,i = 1,2. The following characterization theorem is established: Let , d2. SetS is a compact union of two starshaped sets if and only if there is a sequence {S _j } converging toS (relative to the Hausdorff metric) such that each setS _j satisfies propertyK ₂. For , the sufficiency of the condition above still holds, although the necessity fails.     

The generic contact of convex bodies with circumscribed homothets of a convex surface

LetS ₀ be a convex surface ind-dimensional Euclidean spaceE ^d . Then, ifS ₀ is smooth and strictly convex, we prove that the typical convex body touches the convex suface circumscribed about it and homothetic toS ₀ at preciselyd+1 points.     

Sequentially equidistant points in metric spaces

A sequence (z ₀,z ₁,z ₂,, ...,z _n, z _n+1) of points fromp=z ₀ toq=z _n+1 in a metric spaceX is said to besequentially equidistant ifd(z _i−1,z _i)=d(z _i,z _i+1) for 1≦i≦n. If there is path inX fromp toq (or if a certain weaker condition holds), then such a sequence exists, with all points distinct, for every choice ofn, while ifX is compact and connected, then such a sequence exists at least forn=2. An example is given of a dense connected subspaceS ofR ^m ,m≧2, and an uncountable dense subsetE disjoint fromS for which there is no sequentially equidistant sequence of distinct points (n ≧ 2) inS ∪E between any two points ofE. Techniques of dimension theory are utilized in the construction of these examples, as well as in the proofs of some of the positive results. Supported in part by NSF Grant DMS-8701666.     

On sets having finitely many points of local nonconvexity and propertyP m

If a pointq ofS has the property that each neighborhood ofq contains pointsx andy such that the segmentxy is not contained byS, q is called a point of local nonconvexity ofS. LetQ denote the set of points of local nonconvexity ofS. Tietze’s well known theorem that a closed connected setS in a linear topological space is convex ifQ=φ is generalized in the result:If S is a closed set in a linear topological space such that S ∼ Q is connected and |Q|=n<∞,then S is the union of n+1or fewer closed convex sets. Letk be the minimal number of convex sets needed in a convex covering ofS. Bounds fork in terms ofm andn are obtained for sets having propertyP _m and |Q|=n.     

Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.     

On the expected number of k-sets

Given a setS ofn points inR ^d , a subsetX of sized is called ak-simplex if the hyperplane aff(X) has exactlyk points on one side. We studyE _d (k,n), the expected number of k-simplices whenS is a random sample ofn points from a probability distributionP onR ^d . WhenP is spherically symmetric we prove thatE _d (k, n)≤cn ^d−1 WhenP is uniform on a convex bodyK⊂R ² we prove thatE ₂ (k, n) is asymptotically linear in the rangecn≤k≤n/2 and whenk is constant it is asymptotically the expected number of vertices on the convex hull ofS. Finally, we construct a distributionP onR ² for whichE ₂((n−2)/2,n) iscn logn. The authors express gratitude to the NSF DIMACS Center at Rutgers and Princeton. The research of I. Bárány was supported in part by Hungarian National Science Foundation Grants 1907 and 1909, and W. Steiger's research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

AnR danalogue of Valentine’s theorem on 3-convex sets

This paper deals with anR ^danalogue of a theorem of Valentine which states that a closed 3-convex setS in the plane is decomposable into 3 or fewer closed convex sets. In Valentine’s proof, the points of local nonconvexity ofS are treated as vertices of a polygonP contained in the kernel ofS, yielding a decomposition ofS into 2 or 3 convex sets, depending on whetherP has an even or odd number of edges. Thus the decomposition actually depends onc(P′), the chromatic number of the polytopeP′ dual toP. A natural analogue of this result is the following theorem: LetS be a closed subset ofR ^d, and letQ denote the set of points of local nonconvexity ofS. We require thatQ be contained in the kernel ofS and thatQ coincide with the set of points in the union of all the (d − 2)-dimensional faces of somed-dimensional polytopeP. ThenS is decomposable intoc(P′) closed convex sets.     

Cantor-Bendixson degrees and convexity in ℝ2

We present an ordinal rank, δ³, which refines the standard classification of non-convexity among closed planar sets. The class of closed planar sets falls into a hierarchy of order type ω₁ + 1 when ordered by δ-rank. The rank δ³ (S) of a setS is defined by means of topological complexity of 3-cliques in the set. A 3-clique in a setS is a subset ofS all of whose unordered 3-tuples fail to have their convex hull inS. Similarly, δⁿ (S) is defined for alln>1. The classification cannot be done using δ², which considers only 2-cliques (known in the literature also as “visually independent subsets”), and in dimension 3 or higher the analogous classification is not valid.     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

Necessary and sufficient conditions for stability of effectivity functions

An effectivity functionE assigns to every coalitionS of players a familyE (S) of subsetsB of an outcome setA such thatS can force the outcome to belong to any of the setsB inE (S). The effectivity functionE is stable if for every preference profile there is an outcomex with the property that there is no coalitionS and subsetB ofA such thatB εE (S) and each player inS prefers everyy εB tox. The paper gives a necessary and sufficient condition for an effectivity function to be stable.     

On the structure of cluster point sets of iteratively generated sequences

LetX be a closed subset of a topological spaceF; leta(·) be a continuous map fromX intoX; let {x _i} be a sequence generated iteratively bya(·) fromx ₀ inX, i.e.,x _i+1 =a(x _i),i=0, 1, 2, ...; and letQ(x ₀) be the cluster point set of {x _i}. In this paper, we prove that, if there exists a pointz inQ(x ₀) such that (i)z is isolated with respect toQ(x ₀), (ii)z is a periodic point ofa(·) of periodp, and (iii)z possesses a sequentially compact neighborhood, then (iv)Q(x ₀) containsp points, (v) the sequence {x _i} is contained in a sequentially compact set, and (vi) every point inQ(x ₀) possesses properties (i) and (ii). The application of the preceding results to the caseF=E ⁿ leads to the following: (vii) ifQ(x ₀) contains one and only one point, then {x _i} converges; (viii) ifQ(x ₀) contains a finite number of points, then {x _i} is bounded; and (ix) ifQ(x ₀) containsp points, then every point inQ(x ₀) is a periodic point ofa(·) of periodp.     

On the dimension of ordered sets with the 2-cutset property

An ordered setP is said to have 2-cutset property if, for every elementx ofP, there is a setS of elements ofP which are noncomparable tox, with |S|?2, such that every maximal chain inP meets {x}∪S. We consider the following question: Does there exist ordered sets with the 2-cutset property which have arbitrarily large dimension? We answer the question in the negative by establishing the following two results.Theorem: There are positive integersc andd such that every ordered setP with the 2-cutset property can be represented asP=X∪Y, whereX is an ordinal sum of intervals ofP having dimension ?d, andY is a subset ofP having width ?c. Corollary: There is a positive integern such that every ordered set with the 2-cutset property has dimension ?n.     

AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem

The input to the asymmetricp-center problem consists of an integerpand ann × ndistance matrixDdefined on a vertex setVof sizen, whered_ijgives the distance fromitoj. The distances are assumed to obey the triangle inequality. For a subsetS Vthe radius ofSis the minimum distanceRsuch that every point inVis at a distance at mostRfrom some point inS. Thep-center problem consists of picking a setS Vof sizepto minimize the radius. This problem is known to be NP-complete.For the symmetric case, whend_ij = d_ji, approximation algorithms that deliver a solution to within 2 of the optimal are known. David Shmoys, in his article [[11]], mentions that nothing was known about the asymmetric case. We present an algorithm that achieves a ratio ofO(log*n).     

Multiterminal xcut problems

Ani-j xcut of a setV={1, ...,n} is defined to be a partition ofV into two disjoint nonempty subsets such that bothi andj are contained in the same subset. When partitions are associated with costs, we define thei-j xcut problem to be the problem of computing ani-j xcut of minimum cost. This paper contains a proof that the minimum xcut problems have at mostn distinct optimal solution values. These solutions can be compactly represented by a set ofn partitions in such a way that the optimal solution to any of the problems can be found inO(n) time. For a special additive cost function that naturally arises in connection to graphs, some interesting properties of the set of optimal solutions that lead to a very simple algorithm are presented.     

Sets in a euclidean space which are not a countable union of convex subsets

We prove that if a closed planar setS is not a countable union of convex subsets, then exactly one of the following holds: