On k-convex polygons

DOI10.1016/J.COMGEO.2011.09.001zbMATH Open1244.52005arXiv1007.3607OpenAlexW1585578196MaRDI QIDQ427049FDOQ427049

Authors: Erik D. Demaine, Ferran Hurtado, Oswin Aichholzer, J. Urrutia, Franz Aurenhammer, Pedro Ramos 

Publication date: 13 June 2012

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: We introduce a notion of $k$-convexity and explore polygons in the plane that have this property. Polygons which are mbox{$k$-convex} can be triangulated with fast yet simple algorithms. However, recognizing them in general is a 3SUM-hard problem. We give a characterization of mbox{$2$-convex} polygons, a particularly interesting class, and show how to recognize them in mbox{$O(nlogn)$} time. A description of their shape is given as well, which leads to ErdH{o}s-Szekeres type results regarding subconfigurations of their vertex sets. Finally, we introduce the concept of generalized geometric permutations, and show that their number can be exponential in the number of mbox{$2$-convex} objects considered.

Full work available at URL: https://arxiv.org/abs/1007.3607

Recommendations

• On \(k\)-convex point sets
• On Erdős-Szekeres-type problems for \(k\)-convex point sets
• On Erdős-Szekeres-type problems for \(k\)-convex point sets
• Counting convex \(k\)-gons in planar point sets
• Convex Polygons in Geometric Triangulations

zbMATH Keywords

convexitytransversal theoryvisibility

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Erd?s problems and related topics of discrete geometry (52C10) General topics in the theory of algorithms (68W01)

Cites Work

• On a class of \(O(n^ 2)\) problems in computational geometry
• Title not available (Why is that?)
• The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
• Self-adjusting binary search trees
• Title not available (Why is that?)
• On functional separately convex hulls
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pseudo-triangulations -- a survey
• Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
• Triangulation and shape-complexity
• Triangulating Simple Polygons and Equivalent Problems
• Triangulating and guarding realistic polygons
• Visibility in semi-convex spaces
• Large empty convex polygons in \(k\)-convex sets
• On geodesic properties of polygons relevant to linear time triangulation
• General decomposition theorems for m-convex sets in the plane
• Ray shooting in polygons using geodesic triangulations
• Fundamentals of restricted-orientation convexity
• Modem illumination of monotone polygons
• A sufficient condition for the existence of large empty convex polygons
• A note on convex decompositions of a set of points in the plane
• On \(k\)-convex point sets
• Coverage with \(k\)-transmitters in the presence of obstacles
• Convex Partitions of Graphs
• Title not available (Why is that?)
• Design and Analysis of a Data Structure for Representing Sorted Lists
• An Optimal Algorithm for Finding the Kernel of a Polygon
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A three point convexity property

Cited In (20)

• Necklaces and convex \(k\)-gons
• Rigid polyboxes and Keller's conjecture
• The Katchalski-Lewis transversal problem for regular polygons
• On Inducing Polygons and Related Problems
• Which \(n\)-Venn diagrams can be drawn with convex \(k\)-gons?
• Straight skeletons and mitered offsets of nonconvex polytopes
• Forced convex \(n\)-gons in the plane
• On weighted sums of numbers of convex polygons in point sets
• Geometric quadrangulations of a polygon
• On \(k\)-convex point sets
• On convex polytopes in \(\mathbb R^{d}\) containing and avoiding zero
• On \((k, f,l)\)-chordal polygons
• Title not available (Why is that?)
• On recognizing unions of two convex polygons and related problems
• The Mathematics of Ferran Hurtado: A Brief Survey
• Coverage with \(k\)-transmitters in the presence of obstacles
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Holes in 2-convex point sets
• On Erdős-Szekeres-type problems for \(k\)-convex point sets
• Multi-triangulations as complexes of star polygons

This page was built for publication: On \(k\)-convex polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q427049)