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

DOI10.1016/J.COMGEO.2017.04.002MaRDI QIDQ2401331zbMATHOpenAlexFDO

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

Publication date 8 September 2017

Published in Computational Geometry (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3649571 (Why is no real title available?)
• 4-holes in point sets
• A modular version of the Erdős– Szekeres theorem
• Blocking the \(k\)-holes of point sets in the plane
• Drawing the Horton set in an integer grid of minimum size
• Embedding the double circle in a square grid of minimum size
• Empty convex polygons in almost convex sets
• Large empty convex polygons in \(k\)-convex sets
• Multidimensional Sorting
• On the convex layers of a planar set
• On the generalized Erdös-Szekeres conjecture -- a new upper bound
• Open caps and cups in planar point sets
• Sets with No Empty Convex 7-Gons
• Some notes on the Erdős-Szekeres theorem
• The Complexity of Order Type Isomorphism

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)