On k-convex point sets

O. Aichholzer; F. Aurenhammer; T. Hackl; F. Hurtado; A. Pilz; P. Ramos; J. Urrutia; P. Valtr; B. Vogtenhuber

doi:10.1016/j.comgeo.2014.04.004

On k-convex point sets

O. Aichholzer
, F. Aurenhammer
, T. Hackl
, F. Hurtado
, A. Pilz^*
, P. Ramos
, J. Urrutia
, P. Valtr
, B. Vogtenhuber

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

We extend the (recently introduced) notion of k-convexity of a two-dimensional subset of the Euclidean plane to finite point sets. A set of n points is considered k-convex if there exists a spanning (simple) polygonization such that the intersection of any straight line with its interior consists of at most k disjoint intervals. As the main combinatorial result, we show that every n-point set contains a subset of Ω(log2 n) points that are in 2-convex position. This bound is asymptotically tight. From an algorithmic point of view, we show that 2-convexity of a finite point set can be decided in polynomial time, whereas the corresponding problem on k-convexity becomes NP-complete for any fixed k ≥ 3

Original language	English
Pages (from-to)	809-832
Journal	Computational Geometry: Theory and Applications
Volume	47
Issue number	8
DOIs	https://doi.org/10.1016/j.comgeo.2014.04.004
Publication status	Published - 2014

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Theoretical

Access to Document

10.1016/j.comgeo.2014.04.004

FWF - ComPoSe - EuroGIAG_Erdös-Szekeres type problems for colored point sets and compatible graphs
Aichholzer, O. (Project manager)
1/10/11 → 31/12/15
Project: Research project
FWF - CPGG - Combinatorial Problems on Geometric Graphs
Hackl, T. (Project manager)
1/09/11 → 31/12/15
Project: Research project
Discrete and Computational Geometry
Hackl, T. (Attendee), Vogtenhuber, B. (Attendee), Kornberger, B. (Attendee), Aichholzer, O. (Coordinator), Aigner, W. (Attendee) & Pilz, A. (Attendee)
1/01/05 → 31/12/24
Project: Research area

Cite this

@article{b5356379f7db426bbf5bb583716b2cf9,

title = "On k-convex point sets",

abstract = "We extend the (recently introduced) notion of k-convexity of a two-dimensional subset of the Euclidean plane to finite point sets. A set of n points is considered k-convex if there exists a spanning (simple) polygonization such that the intersection of any straight line with its interior consists of at most k disjoint intervals. As the main combinatorial result, we show that every n-point set contains a subset of Ω(log2 n) points that are in 2-convex position. This bound is asymptotically tight. From an algorithmic point of view, we show that 2-convexity of a finite point set can be decided in polynomial time, whereas the corresponding problem on k-convexity becomes NP-complete for any fixed k ≥ 3",

author = "O. Aichholzer and F. Aurenhammer and T. Hackl and F. Hurtado and A. Pilz and P. Ramos and J. Urrutia and P. Valtr and B. Vogtenhuber",

year = "2014",

doi = "10.1016/j.comgeo.2014.04.004",

language = "English",

volume = "47",

pages = "809--832",

journal = "Computational Geometry: Theory and Applications",

issn = "1879-081X",

publisher = "Elsevier B.V.",

number = "8",

}

TY - JOUR

T1 - On k-convex point sets

AU - Aichholzer, O.

AU - Aurenhammer, F.

AU - Hackl, T.

AU - Hurtado, F.

AU - Pilz, A.

AU - Ramos, P.

AU - Urrutia, J.

AU - Valtr, P.

AU - Vogtenhuber, B.

PY - 2014

Y1 - 2014

N2 - We extend the (recently introduced) notion of k-convexity of a two-dimensional subset of the Euclidean plane to finite point sets. A set of n points is considered k-convex if there exists a spanning (simple) polygonization such that the intersection of any straight line with its interior consists of at most k disjoint intervals. As the main combinatorial result, we show that every n-point set contains a subset of Ω(log2 n) points that are in 2-convex position. This bound is asymptotically tight. From an algorithmic point of view, we show that 2-convexity of a finite point set can be decided in polynomial time, whereas the corresponding problem on k-convexity becomes NP-complete for any fixed k ≥ 3

AB - We extend the (recently introduced) notion of k-convexity of a two-dimensional subset of the Euclidean plane to finite point sets. A set of n points is considered k-convex if there exists a spanning (simple) polygonization such that the intersection of any straight line with its interior consists of at most k disjoint intervals. As the main combinatorial result, we show that every n-point set contains a subset of Ω(log2 n) points that are in 2-convex position. This bound is asymptotically tight. From an algorithmic point of view, we show that 2-convexity of a finite point set can be decided in polynomial time, whereas the corresponding problem on k-convexity becomes NP-complete for any fixed k ≥ 3

U2 - 10.1016/j.comgeo.2014.04.004

DO - 10.1016/j.comgeo.2014.04.004

M3 - Article

SN - 1879-081X

VL - 47

SP - 809

EP - 832

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 8

ER -

On k-convex point sets

Abstract

Fields of Expertise

Treatment code (Nähere Zuordnung)

Access to Document

Fingerprint

Projects

FWF - ComPoSe - EuroGIAG_Erdös-Szekeres type problems for colored point sets and compatible graphs

FWF - CPGG - Combinatorial Problems on Geometric Graphs

Discrete and Computational Geometry

Cite this