No Krasnoselskii Number for General Sets

Authors Chaya Keller, Micha A. Perles



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.47.pdf
  • Filesize: 0.69 MB
  • 11 pages

Document Identifiers

Author Details

Chaya Keller
  • Department of Computer Science, Ariel University, Israel
Micha A. Perles
  • Einstein Institute of Mathematics, Hebrew University, Jerusalem, Israel

Cite AsGet BibTex

Chaya Keller and Micha A. Perles. No Krasnoselskii Number for General Sets. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 47:1-47:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.47

Abstract

For a family ℱ of non-empty sets in ℝ^d, the Krasnoselskii number of ℱ is the smallest m such that for any S ∈ ℱ, if every m or fewer points of S are visible from a common point in S, then any finite subset of S is visible from a single point. More than 35 years ago, Peterson asked whether there exists a Krasnoselskii number for general sets in ℝ^d. The best known positive result is Krasnoselskii number 3 for closed sets in the plane, and the best known negative result is that if a Krasnoselskii number for general sets in ℝ^d exists, it cannot be smaller than (d+1)². In this paper we answer Peterson’s question in the negative by showing that there is no Krasnoselskii number for the family of all sets in ℝ². The proof is non-constructive, and uses transfinite induction and the well-ordering theorem. In addition, we consider Krasnoselskii numbers with respect to visibility through polygonal paths of length ≤ n, for which an analogue of Krasnoselskii’s theorem for compact simply connected sets was proved by Magazanik and Perles. We show, by an explicit construction, that for any n ≥ 2, there is no Krasnoselskii number for the family of compact sets in ℝ² with respect to visibility through paths of length ≤ n. (Here the counterexamples are finite unions of line segments.)

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • visibility
  • Helly-type theorems
  • Krasnoselskii’s theorem
  • transfinite induction
  • well-ordering theorem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. J. Borwein. A proof of the equivalence of Helly’s and Krasnosselsky’s theorems. Canad. Math. Bull., 20:35-37, 1977. Google Scholar
  2. M. Breen. Clear visibility, starshaped sets, and finitely starlike sets. J. Geometry, 19:183-196, 1982. Google Scholar
  3. M. Breen. Krasnoselskii-type theorems. Ann. New York Acad. Sci., 440:142-146, 1985. Google Scholar
  4. M. Breen. Some Krasnosel’skii numbers for finitely starlike sets in the plane. J. Geometry, 32:1-12, 1988. Google Scholar
  5. M. Breen. Finitely starlike sets whose F-stars have positive measure. J. Geometry, 35:19-25, 1989. Google Scholar
  6. M. Breen. A family of examples showing that no Krasnosel’skii number exists for orthogonal polygons starhaped via staircase n-paths. J. Geometry, 94:1-6, 2009. Google Scholar
  7. A. M. Bruckner and J. B. Bruckner. On L_n sets, the Hausdorff metric, and connectedness. Proc. Amer. Math. Soc., 13:765-767, 1962. Google Scholar
  8. H. T. Croft, K. J. Falconer, and R. K. Guy. Unsolved problems in geometry, Volume II. Springer, 1990. Google Scholar
  9. P. Erdős and G. Purdy. Extremal problems in discrete geometry. In R. L. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics. North Holland, 1995. Google Scholar
  10. A. Horn and F. A. Valentine. Some properties of L-sets in the plane. Duke Math. J., 16:131-140, 1949. Google Scholar
  11. T. Jech. Set theory: The third Milennium edition. Springer, 2003. Google Scholar
  12. M. A. Krasnoselskii. Sur un critère pour qu'un domain soit Étoilé. Math. Sb., 19:309-310., 1946. Google Scholar
  13. A. Levy. Basic set theory. Springer-Verlag, Berlin, 1979. Google Scholar
  14. E. Magazanik and M. A. Perles. Generalized convex kernels of simply connected L_n sets in the plane. Israel J. Math., 160:157-171, 2007. Google Scholar
  15. B. Peterson. Is there a Krasnonsel’skii theorem for finitely starlike sets? In M. Breen and David C. Kay, editors, Convexity and related combinatorial geometry. Marcel Dekker, New York, 1982. Google Scholar
  16. Y. Shlezinger. Krasnoselskii numbers for finitely starlike sets, m.sc. thesis, hebrew university, 2011. Google Scholar
  17. F. A. Valentine. Local convexity and L_n sets. Proc. Amer. Math. Soc., 16:1305-1310, 1965. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail