Fulltext

On Polygons Excluding Point Sets

Fulek, Radoslav ; Keszegh, Balázs ; Morić, Filip ; Uljarević, Igor

In: Graphs and Combinatorics, 2013, vol. 29, no. 6, p. 1741-1753

Add to personal list
    Title
    • On Polygons Excluding Point Sets
    Author
    • Fulek, Radoslav. Faculté de Sciences de Base, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
    • Keszegh, Balázs. Faculté de Sciences de Base, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
    • Morić, Filip. Faculté de Sciences de Base, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
    • Uljarević, Igor. Matematički fakultet, Univerzitet u Beograd, Belgrade, Serbia
    Document Type
    • Postprint
    OAI-PMH Identifier
    • oai:doc.rero.ch:319858
    Summary
    By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that $${B\cup R}$$ is in general position, and the convex hull of B contains k interior blue points and l interior red points. Hurtado etal. found sufficient conditions for the existence of a blue polygonization that encloses all red points. We consider the dual question of the existence of a blue polygonization that excludes all red points R. We show that there is a minimal number K=K(l), which is bounded from above by a polynomial in l, such that one can always find a blue polygonization excluding all red points, whenever k≥ K. Some other related problems are also considered