Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. On Polygons Excluding Point Sets
 
research article

On Polygons Excluding Point Sets

Fulek, Radoslav  
•
Keszegh, Balazs  
•
Moric, Filip  
Show more
2013
Graphs And Combinatorics

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 is in general position, and the convex hull of B contains k interior blue points and l interior red points. Hurtado et al. 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 a parts per thousand yen K. Some other related problems are also considered.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

373_2012_Article_1221.pdf

Type

Publisher's Version

Version

Published version

Access type

openaccess

Size

443.8 KB

Format

Adobe PDF

Checksum (MD5)

28255165a5c3060bc6cfdc1fb27e8bad

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés