A Helly-type theorem for intersections of certain orthogonal polytopes starshaped via k -staircase paths
- PDF / 257,211 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 85 Downloads / 140 Views
A Helly-type theorem for intersections of certain orthogonal polytopes starshaped via k-staircase paths Marilyn Breen1 Received: 12 July 2019 / Accepted: 16 March 2020 © The Managing Editors 2020
Abstract Let K be a finite family of orthogonal polytopes in Rd such that, for every nonempty subfamily K of K, ∩{K : K in K }, if nonempty, is a finite union of boxes whose intersection graph is a tree. Let k and n be fixed integers, 1 ≤ k ≤ 2n . Assume that certain visibility sets have connected intersections and that, for every 2(d + 1)n+1 (or fewer) member subset K of K, ∩{K : K in K } is nonempty and starshaped via k-staircase paths. Then ∩{K : K in K} is nonempty and starshaped via k-staircase paths as well. Keywords Orthogonal polytope · Starshaped via k-staircase paths · Helly-type theorem Mathematics Subject Classification 52.A30 · 52.A35
1 Introduction We begin with a short introduction to the problem. Precise definitions for the corresponding concepts appear in Sect. 2. Many results in convexity that involve the usual notion of visibility via straight line segments have interesting analogues that instead use the idea of visibility via staircase paths. For example, the familiar Krasnosel’skii theorem (Krasnosel’skii 1946) says that, for S a nonempty compact set in the plane, S is starshaped via segments if and only if every three points of S see via segments in S a common point. In the staircase analogue (Breen 1994), for S a nonempty simply connected orthogonal polygon in the plane, S is staircase starshaped if and only if every two points of S see via staircase paths in S a common point. Moreover, in an interesting study involving median graphs as well as median polyhedra in the rectilinear space Rd , Chepoi (1996) has generalized
B 1
Marilyn Breen [email protected] The University of Oklahoma, Norman, OK 73019, USA
123
Beitr Algebra Geom
the planar result to any finite union of boxes in Rd whose corresponding intersection graph is a tree. As he observes, every simply connected orthogonal polygon may be expressed as such a union. Appropriately, the staircase kernel of such a set will be staircase convex (Breen 2015, Theorem 1). Results in Breen (2020) examine analogous problems for k-staircase paths. Again let S be a finite union of boxes in Rd whose intersection graph is a tree. For each point x of S, define the associated k-visibility set Vk (x) to be the subset of S seen by x via k-staircase paths. If every two points of S see a common point via k-staircase paths (that is, if every two of the k-visibility sets intersect), then S will be starshaped via k-staircase paths, providing a Krasnosel’skii-type theorem for S that is a direct analogue of the earlier staircase path result. In addition, the corresponding k-kernel K erk S will be convex via k-staircase paths. In this paper, we turn our attention to the following Helly-type theorem by Bobylev (2001): For K a family of compact sets in Rd , if every d + 1 (not necessarily distinct) members of K have an intersection that is nonempty and starshaped (v
Data Loading...
