Drawing the almost convex set in an integer grid of minimum size

DOI10.1016/J.COMGEO.2017.04.002zbMATH Open1373.52022arXiv1606.02328OpenAlexW2963699656MaRDI QIDQ2401331FDOQ2401331

P. Pérez-Lantero, Carlos Hidalgo-Toscano, Frank Duque, R. Fabila-Monroy

Publication date: 8 September 2017

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

Abstract: In 2001, K'arolyi, Pach and T'oth introduced a family of point sets to solve an ErdH{o}s-Szekeres type problem; which have been used to solve several other EdH{o}s-Szekeres type problems. In this paper we refer to these sets as nested almost convex sets. A nested almost convex set $mathcalX$ has the property that the interior of every triangle determined by three points in the same convex layer of $mathcalX$, contains exactly one point of $mathcalX$. In this paper, we introduce a characterization of nested almost convex sets. Our characterization implies that there exists at most one (up to order type) nested almost convex set of $n$ points. We use our characterization to obtain a linear time algorithm to construct nested almost convex sets of $n$ points, with integer coordinates of absolute values at most $O(n^{lo{g}_{2}5})$. Finally, we use our characterization to obtain an $O(nlogn)$-time algorithm to determine whether a set of points is a nested almost convex set.

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

Recommendations

• Empty convex polygons in almost convex sets
• On the Erdős-Szekeres \(n\)-interior-point problem
• Point sets with small integer coordinates and no large convex polygons
• On Erdős-Szekeres-type problems for \(k\)-convex point sets
• On Erdős-Szekeres-type problems for \(k\)-convex point sets

zbMATH Keywords

holeinteger gridalmost convex set

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Erd?s problems and related topics of discrete geometry (52C10) Other problems of combinatorial convexity (52A37)

Cites Work

• A modular version of the Erdős– Szekeres theorem
• 4-holes in point sets
• Title not available (Why is that?)
• Sets with No Empty Convex 7-Gons
• Multidimensional Sorting
• Large empty convex polygons in \(k\)-convex sets
• On the convex layers of a planar set
• Blocking the \(k\)-holes of point sets in the plane
• Empty convex polygons in almost convex sets
• On the generalized Erdös-Szekeres conjecture -- a new upper bound
• Some notes on the Erdős-Szekeres theorem
• Drawing the Horton set in an integer grid of minimum size
• EMBEDDING THE DOUBLE CIRCLE IN A SQUARE GRID OF MINIMUM SIZE
• The Complexity of Order Type Isomorphism
• Open caps and cups in planar point sets

Cited In (2)

• Graph Drawing
• Empty convex polygons in almost convex sets

This page was built for publication: Drawing the almost convex set in an integer grid of minimum size

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