Unions of orthogonally convex or orthogonally starshaped polygons. (English) Zbl 0814.52002

Breen, Marilyn

Geom. Dedicata 53, No. 1, 49-56 (1994).

This paper considers orthogonal polygons obtained as union of finitely many convex polygons whose edges are parallel to the coordinate axes. A simple polygonal path in the plane whose edges are finite and parallel to the coordinate axes is called a staircase path iff the associated vectors alternate in direction. A set \(T\) is said to be an orthogonally convex polygon iff for all \([x,y]\) in \(T\) such that \([x,y]\) is either horizontal or vertical, then \([x,y] \subseteq T\). A set \(T\) is starshaped via staircase paths with respect to a point \(p\) iff \(p\) sees each point of \(T\) via staircase paths. By imposing conditions on finite subsets of a set \(T\) in a linear space, J. F. Lawrence, W. R. Hare jun. and John W. Kenelly [Proc. Am. Math. Soc. 34, 225-288 (1972; Zbl 0237.52001)] have characterized \(T\) as union of finite number of convex sets. The author in her first theorem obtains a similar result for simply connected orthogonal polygons in the plane. In the theorem it is stated that the necessary and sufficient condition for a simply connected orthogonal polygon in the plane to be a union of \(k\) orthogonally convex sets is that for every finite subset \(F\) of \(T\) there exists a \(k\)- partition \(\{F_ i\}_{1 \leq i \leq k}\) of \(F\) such that every pair of points in \(F_ i\) can be joined by a staircase path in \(T\). In the second theorem the author proves that if a simply connected orthogonal polygon having that for every three points of \(T\), at least two of these see each other via staircase paths in \(T\), the set is a union of three orthogonally convex polygons. In Theorem 3 the necessary and sufficient condition for a decomposition of a simple connected orthogonal polygon in the plane into two orthogonally convex polygons is given by introducing an odd numbered finite point sequence \(\{\nu_ i\}\) where \(\nu_{n + 1} = \nu_ 1\), \(1 \leq i \leq n\) in the set such that at least one consecutive pair of points see each other via staircase paths belonging to the set. Theorem 4 states that a simply connected orthogonal polygon \(T\) in the plane is a union of \(k\)-orthogonal polygons, each one starshaped via staircase paths, iff there exists a \(k\)-partition \(\{F_ i\}\) of \(F\) such that every pair in \(F_ i\) sees a common point of \(T\) via staircase paths. In the last theorem, the author expresses a necessary and sufficient condition for a simply connected orthogonal polygon to be the union of two orthogonal polygons, each one starshaped via staircase paths, by substituting the \(k\)-partition of a finite subset with point sequences \(\nu_ i,\dots,\nu_{n + 1} = \nu_ 1\), \(n\) odd, such that at least one consecutive pair of points sees a common point via staircase paths in \(T\).

Reviewer: S.Abdoǧan (İstanbul)

MSC:

52A30	Variants of convex sets (star-shaped, (\(m, n\))-convex, etc.)
51A35	Non-Desarguesian affine and projective planes

Keywords:

orthogonal polygons; staircase path; orthogonally convex; starshaped

Citations:

Zbl 0237.52001

References:

[1]	Breen, M.: A Krasnosel’skii theorem for staircase paths in orthogonal polygons,J. Geom. (to appear). · Zbl 1298.52008
[2]	Breen, M.: An improved Krasnosel’skii-type theorem for orthogonal polygons which are starshaped via staircase paths,J. Geom. (to appear). · Zbl 0815.52005
[3]	Breen, M.: Staircase kernels in orthogonal polygons,Arch. Math. 59 (1992), 588-594. · Zbl 0789.52011
[4]	Danzer, L., Grünbaum, B. and Klee, V.: Helly’s theorem and its relatives,Convexity, Proc. Sympos. Pure Math. 7 (1962),Amer. Math. Soc., Providence, RI, pp. 101-180. · Zbl 0132.17401
[5]	Harary, F.:Graph Theory, Addison Wesley, Reading, Mass., 1972. · Zbl 0235.05105
[6]	Hare, W.R., Jr and Kenelly, J. W.: Sets expressible as unions of two convex sets,Proc. Amer. Math. Soc. 25 (1970), 379-380. · Zbl 0195.51603
[7]	Lawrence, J. F., Hare, W. R. Jr and Kenelly, J. W.: Finite unions of convex sets,Proc. Amer. Math. Soc. 34 (1972), 225-228. · Zbl 0237.52001
[8]	Lay, S. R.:Convex Sets and Their Applications, Wiley, New York, 1982. · Zbl 0492.52001
[9]	McKinney, R. L.: On unions of two convex sets,Canad. J. Math. 18 (1966), 883-886. · Zbl 0173.15305
[10]	Molnàr, J.: Über den zweidimensionalen topologischen Satz von Helly,Mat. Lapok 8 (1957), 108-114. · Zbl 0105.16705
[11]	Motwani, R., Raghunathan, A. and Saran, H.: Covering orthogonal polygons with star polygons: the perfect graph approach,J. Comput. System Sci. 40 (1990), 19-48. · Zbl 0705.68082
[12]	Nadler, S.:Hyperspaces of Sets, Marcel Dekker, New York, 1978.
[13]	Valentine, F. A.: A three point convexity property,Pacific J. Math. 7 (1957), 1227-1235. · Zbl 0080.15401
[14]	Valentine, F. A.:Convex Sets, McGraw-Hill, New York, 1964. · Zbl 0129.37203