Sets associated with the farthest point problem

LetS be a convex compact set in a normed linear spaceX. For each cardinal numbern, defineS _n = {x X:x has exactlyn farthest points inS} andT _n = _kn S _k. It is shown that ifX =E thenT ₃ is countable andT ₂ is contractible to a point. Properties of associated level curves are given.     

Illumination by translates of convex sets

Let S be a compact set in the plane. If every three points of S are illuminated clearly by some translate of the compact convex set T, then there is a translate of T which illumines every point of S. Various analogues hold for translates of flats in R ^das well.Supported in part by NSF grant DMS-8705336.     

ℒ2 sets which are almost starshaped

Let S be a subset of R ^d . The set S is said to be an set if and only if for every two points x and y of S, there exists some z S such that [x, z] [z, y] S. Clearly every starshaped set is an set, yet the converse is false and introduces an interesting question: Under what conditions will an set S be almost starshaped; that is, when will there exist a convex subset C of S such that every point of S sees some point of C via SThis paper provides one answer to the question above, and we have the following result: Let S be a closed planar set, S simply connected, and assume that the set Q of points of local nonconvexity of S is finite. If some point p of S see each member of Q via S, then there is a convex subset C of S such that every point of S sees some point of C via S.     

Sets determined by finitely many X-rays

A measurable set in _n which is uniquely determined among all measurable sets (modulo null sets) by its X-rays in a finite set L of directions, or more generally by its X-rays parallel to a finite set L of subspaces, is called L-unique, or simply unique. Some subclasses of the L-unique sets are known. The L-additive sets are those measurable sets E which can be written E {x _n : _i f _i (x) * 0}. Here, denotes equality modulo null sets, * is either or >, and the terms in the sum are the values of ridge functions f _i orthogonal to subspaces S _i in L. If n=2, the L-inscribable convex sets are those whose interiors are the union of interiors of inscribed convex polygons, all of whose sides are parallel to the lines in L. Relations between these classes are investigated. It is shown that in _n each L-inscribable convex set is L-additive, but L-additive convex sets need not be L-inscribable. It is also shown that every ellipsoid in _n is unique for any set of three directions. Finally, some results are proved concerning the structure of convex sets in _n , unique with respect to certain families of coordinate subspaces.     

Points of local nonconvexity and sets which are almost starshaped

Let Sø be a bounded connected set in R ², and assume that every 3 or fewer lnc points of S are clearly visible from a common point of S. Then for some point p in S, the set A{s : s in S and [p, s] S} is nowhere dense in S. Furthermore, when S is open, then S in starshaped.     

A monotonicity lemma in higher dimensions

Let K be a body of constant width in a Minkowski space (i.e., in a real finite dimensional Banach space). Then any hyperplane section S of K bounds two parts of K one of which has the same diameter as S. Furthermore, if we represent K as the union of hyperplane sections S(t), t ∈[0, 1], continuously depending on t, then the Minkowskian diameter of S(t) is a unimodal function of the variable t. These two statements (being the core of this note) can be considered as higher-dimensional extensions of the well-known monotonicity lemma from Minkowski geometry.     

Convexity in finite metric spaces

A subsetS of a metric space (X,d) is calledd-convex if for any pair of pointsx,y S each pointz X withd(x,z) +d(z,y) =d(x,y) belongs toS. We give some results and open questions concerning isometric and convexity-preserving embeddings of finite metric spaces into standard spaces and the number ofd-convex sets of a finite metric space.     

Unions of three starshaped sets in R2

LetS be a compact, simply connected set inR ². If every boundary point ofS is clearly visible viaS from at least one of the three pointsa, b, c, thenS is a union of three starshaped sets whose kernels containa, b, c, respectively. The result fails when the number three is replaced by four.As a partial converse, ifS is a union of three starshaped sets whose kernels containa, b, c, respectively, then the set of points in the boundary ofS clearly visible from at least one ofa, b, orc is dense in the boundary ofS.Supported in part by NSF grant DMS-8705336.     

The dimension of the kernel in an intersection of starshaped sets

We establish the following Helly-type theorem: Let ${\cal K}$ be a family of compact sets in $\mathbb{R}^d$. If every d + 1 (not necessarily distinct) members of ${\cal K}$ intersect in a starshaped set whose kernel contains a translate of set A, then $\cap \{ K : K\; \hbox{in}\; {\cal K} \}$ also is a starshaped set whose kernel contains a translate of A. An analogous result holds when ${\cal K}$ is a finite family of closed sets in $\mathbb{R}^d$. Moreover, we have the following planar result: Define function f on $\{0, 1, 2\}$ by f(0) = f(2) = 3, f(1) = 4. Let ${\cal K}$ be a finite family of closed sets in the plane. For k = 0, 1, 2, if every f(k) (not necessarily distinct) members of ${\cal K}$ intersect in a starshaped set whose kernel has dimension at least k, then $\cap \{K : K\; \hbox{in}\; {\cal K}\}$ also is a starshaped set whose kernel has dimension at least k. The number f(k) is best in each case.Received: 4 June 2002     

On illumination in the plane by line segments

We show that S E ² contains a line segment illuminator if any two points of S are illuminated by a line segment of S in a given direction or if any eight points of S are illuminated by a connected set of line segments of S and a certain connectedness condition is fulfilled. We also show that if any three points of S E ² are illuminated by a translate in S of a line segment T, then S contains a line segment illuminator, which is also a translate of T. As a further result, we have that if any three points of a polygon P are illuminated by some line segment of P then the so-called link center of P illuminates P. Finally, we prove that if any three points of an o-symmetric polygon P are illuminated by a line segment of P through the point o then P contains an o-symmetric convex illuminator which is either a line segment or a parallelogram.Partially supported by the Hungarian National Foundation for Scientific Research grant number 1238.Partially supported by the Natural Sciences and Engineering Research Council of Canada.     

Approximating Minimum-Weight Triangulations in Three Dimensions

Let S be a set of noncrossing triangular obstacles in R ³ with convex hull H . A triangulation T of H is compatible with S if every triangle of S is the union of a subset of the faces of T. The weight of T is the sum of the areas of the triangles of T. We give a polynomial-time algorithm that computes a triangulation compatible with S whose weight is at most a constant times the weight of any compatible triangulation. One motivation for studying minimum-weight triangulations is a connection with ray shooting. A particularly simple way to answer a ray-shooting query (``Report the first obstacle hit by a query ray') is to walk through a triangulation along the ray, stopping at the first obstacle. Under a reasonably natural distribution of query rays, the average cost of a ray-shooting query is proportional to triangulation weight. A similar connection exists for line-stabbing queries (``Report all obstacles hit by a query line'). Received February 3, 1997, and in revised form August 21, 1998.     

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.     

Realizing Sets of Associated Prime Ideals

Let R be a Noetherian ring, and let S be a finite subset of Spec R. We characterize when there exists an ideal I such that S equals the set of associated prime divisors of I.     

Colouring Arcwise Connected Sets in the Plane I

Let ? be the family of finite collections ? where ? is a collection of bounded, arcwise connected sets in ℝ² which for any S, T∈? where S∩T≠∅, it holds that S∩T is arcwise connected. We investigate the problem of bounding the chromatic number of the intersection graph G of a collection ?∈?.  Assuming G is triangle-free, suppose there exists a closed Jordan curve C⊂ℝ² such that C intersects all sets of ? and for all S∈?, the following holds: (i) S∩(C∪int (C)) is arcwise connected or S∩int (C)=∅. (ii) S∩(C∪ext (C)) is arcwise connected or S∩ext (C)=∅.  Here int(C) and ext (C) denote the regions in the interior, resp. exterior, of C. Such being the case, we shall show that χ(?) is bounded by a constant independent of ?. Revised: December 3, 1998     

Finitely starlike sets whose F-stars have positive measure

Let and assume that there is a countable collection of lines {L _i : 1 i} such that (int cl S) and ((int cl S) S) L _i has one-dimensional Lebesgue measure zero, 1 i. Then every 4 point subset ofS sees viaS a set of positive two-dimensional Lebesgue measure if and only if every finite subset ofS sees viaS such a set. Furthermore, a parallel result holds with two-dimensional replaced by one-dimensional. Finally, setS is finitely starlike if and only if every 5 points ofS see viaS a common point. In each case, the number 4 or 5 is best possible.Supported in part by NSF grant DMS-8705336.     

Intersections of Sets Starshaped Via Paths of Bounded Length

 Let S be a nonempty closed, simply connected set in the plane. For α > 0, let ℳ denote the family of all maximal subsets of S which are starshaped via paths of length at most α. Then ⋂{M : M in ℳ} is either starshaped via α-paths or empty. The result fails without the simple connectedness condition. However, even with a simple connectedness requirement, there is no Helly theorem for intersections of sets which are starshaped via α-paths. Received November 19, 2001; in revised form April 25, 2002 Published online November 18, 2002     

Intersections of maximal staircase sets

A compact set is staircase connected if every two points a, b ∈ S can be connected by an x-monotone and y-monotone polygonal path with sides parallel to the coordinate axes. In [5] we have introduced the concepts of staircase k-stars and kernels. In this paper we prove that if the staircase k-kernel is not empty, then it can be expressed as the intersection of a covering family of maximal subsets of staircase diameter k of S.      

Sets satisfying the Central Sets Theorem

Central subsets of a discrete semigroup S have very strong combinatorial properties which are a consequence of the Central Sets Theorem . We investigate here the class of semigroups that have a subset with zero Følner density which satisfies the conclusion of the Central Sets Theorem. We show that this class includes any direct sum of countably many finite abelian groups as well as any subsemigroup of (?,+) which contains ?. We also show that if S and T are in this class and either both are left cancellative or T has a left identity, then S×T is in this class. We also extend a theorem proved in (Beiglböck et al. in Topology Appl., to appear), which states that, if p is an idempotent in β? whose members have positive density, then every member of p satisfies the Central Sets Theorem. We show that this holds for all commutative semigroups. Finally, we provide a simple elementary proof of the fact that any commutative semigroup satisfies the Strong Følner Condition.     

Theories of linear order

LetT be a complete theory of linear order; the language ofT may contain a finite or a countable set of unary predicates. We prove the following results. (i) The number of nonisomorphic countable models ofT is either finite or 2^ω. (ii) If the language ofT is finite then the number of nonisomorphic countable models ofT is either 1 or 2^ω. (iii) IfS ₁(T) is countable then so isS _n(T) for everyn. (iv) In caseS ₁(T) is countable we find a relation between the Cantor Bendixon rank ofS ₁(T) and the Cantor Bendixon rank ofS _n(T). (v) We define a class of modelsL, and show thatS ₁(T) is finite iff the models ofT belong toL. We conclude that ifS ₁(T) is finite thenT is finitely axiomatizable. (vi) We prove some theorems concerning the existence and the structure of saturated models. Most of the results in this paper appeared in the author’s Master of Science thesis which was prepared at the Hebrew University under the supervision of Professor H. Gaifman.     

On the transversal Helly numbers of disjoint and overlapping disks

A family of disks is said to have the property T(k) if any k members of the family have a common line transversal. We call a family of unit diameter disks t-disjoint if the distances between the centers are greater than t. We consider for each natural number k≧ 3 the infimum t_k of the distances t for which any finite family of t-disjoint unit diameter disks with the property T(k) has a line transversal. We determine exact values of t₃ and t₄, and give general lower and upper bounds on the sequence t_k, showing that t_k = O(1/k) as k → ∞. In honour of Helge Tverberg’s seventieth birthday Received: 9 June 2005