Document Open Access Logo

Convex Polygons in Cartesian Products

Authors Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, Sander Verdonschot

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.22.pdf
  • Filesize: 0.61 MB
  • 17 pages

Document Identifiers

Author Details

Jean-Lou De Carufel
  • School of Electrical Engineering and Computer Science, University of Ottawa, Canada
Adrian Dumitrescu
  • Department of Computer Science, University of Wisconsin-Milwaukee, USA
Wouter Meulemans
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Tim Ophelders
  • Department of Computational Mathematics, Science and Engineering, Michigan State University, East Lansing, MI, USA
Claire Pennarun
  • LIRMM, CNRS & Université de Montpellier, France
Csaba D. Tóth
  • Department of Mathematics, California State University Northridge, Los Angeles, CA, USA
  • Department of Computer Science, Tufts University, Medford, MA, USA
Sander Verdonschot
  • School of Computer Science, Carleton University, Ottawa, ON, Canada

Funding

  • Meulemans, Wouter: Partially supported by the Netherlands eScience Center (NLeSC, 027.015.G02)
  • Tóth, Csaba D.: Supported in part by the NSF awards CCF-1422311 and CCF-1423615.

Acknowledgements

This work was initiated at the 2017 Fields Workshop on Discrete and Computational Geometry (Carleton University, Ottawa, ON, July 31 - August 4, 2017).

Cite AsGet BibTex

Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot. Convex Polygons in Cartesian Products. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.22

Abstract

We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of n real numbers (for short, grid). First, we prove that every such grid contains a convex polygon with Omega(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d in N), and obtain a tight lower bound of Omega(log^{d-1}n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the longest convex polygonal chain in a grid that contains no two points with the same x- or y-coordinate. We show that the maximum size of such a convex polygon can be efficiently approximated up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Erdős-Szekeres theorem
  • Cartesian product
  • convexity
  • polyhedron
  • recursive construction
  • approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Imre Bárány. Random points and lattice points in convex bodies. Bulletin of the American Mathematical Society, 45:339-365, 2008. Google Scholar
  2. Imre Bárány and János Pach. On the number of convex lattice polygons. Combinatorics, Probability and Computing, 1(4):295-302, 1992. Google Scholar
  3. Imre Bárány and Anatoly Moiseevich Vershik. On the number of convex lattice polytopes. Geometric and Functional Analysis, 2(4):381-393, 1992. Google Scholar
  4. Alexander Barvinok. Lattice points and lattice polytopes. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 7, pages 185-210. CRC Press, Boca Raton, FL, 3rd edition, 2017. Google Scholar
  5. Boris Bukh and Jiří Matoušek. Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1. Manuscript, 2012. Available from: URL: https://arxiv.org/abs/1207.0705.
  6. Jean Cardinal, Csaba D. Tóth, and David R. Wood. A note on independent hyperplanes and general position subsets in d-space. Journal of Geometry, 108(1):33-43, 2017. Google Scholar
  7. Václav Chvátal and G. T. Klincsek. Finding largest convex subsets. Congressus Numerantium, 29:453-460, 1980. Google Scholar
  8. David Conlon, Jacob Fox, János Pach, Benny Sudakov, and Andrew Suk. Ramsey-type results for semi-algebraic relations. Transactions of the American Mathematical Society, 366:5043-5065, 2014. Google Scholar
  9. Adrian Dumitrescu, André Schulz, Adam Sheffer, and Csaba D. Tóth. Bounds on the maximum multiplicity of some common geometric graphs. SIAM Journal on Discrete Mathematics, 27(2):802-826, 2013. Google Scholar
  10. Herbert Edelsbrunner and Leonidas J. Guibas. Topologically Sweeping an Arrangement. Journal of Computer and System Sciences, 38(1):165-194, 1989. Google Scholar
  11. György Elekes, Melvyn B. Nathanson, and Imre Z. Ruzsa. Convexity and Sumsets. Journal of Number Theory, 83(2):194-201, 2000. Google Scholar
  12. Paul Erdős. Appendix, in Klaus F. Roth, On a problem of Heilbronn. Journal of the London Mathematical Society, 26:198-204, 1951. Google Scholar
  13. Paul Erdős. Some more problems on elementary geometry. Gazette of the Australian Mathematical Society, 5(2):52-54, 1978. Google Scholar
  14. Paul Erdős and György Szekeres. On some extremum problems in elementary geometry. Annales Universitatis Scientiarium Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica, 3-4:53-62, 1960/1961. Google Scholar
  15. Panos Giannopoulos, Christian Knauer, and Daniel Werner. On the Computational Complexity of Erdős-Szekeres and Related Problems in ℝ³. In Proc. 21st European Symposium on Algorithms, volume 8125 of LNCS, pages 541-552. Springer, 2013. Google Scholar
  16. Ronald L. Graham. Euclidean Ramsey theory. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 11, pages 281-297. CRC Press, Boca Raton, FL, 3rd edition, 2017. Google Scholar
  17. Richard K. Guy and Patrick A. Kelly. The No-Three-in-Line-Problem. Canadian Mathematical Bulletin, 11:527-531, 1968. Google Scholar
  18. Norbert Hegyvári. On consecutive sums in sequences. Acta Mathematica Hungarica, 48(1-2):193-200, 1986. Google Scholar
  19. Gyula Károlyi and Pavel Valtr. Configurations in d-space without large subsets in convex position. Discrete &Computational Geometry, 30(2):277-286, 2003. Google Scholar
  20. Joseph S.B. Mitchell, Günter Rote, Gopalakrishnan Sundaram, and Gerhard Woeginger. Counting convex polygons in planar point sets. Information Processing Letters, 56(1):45-49, 1995. Google Scholar
  21. Michael S. Payne and David R. Wood. On the general position subset selection problem. SIAM Journal on Discrete Mathematics, 27(4):1727-1733, 2013. Google Scholar
  22. Attila Pór and David R. Wood. No-three-in-line-in-3D. Algorithmica, 47(4):481-488, 2007. Google Scholar
  23. Orit E. Raz, Micha Sharir, and Ilya D. Shkredov. On the number of unit-area triangles spanned by convex grids in the plane. Computational Geometry: Theory and Applications, 62:25-33, 2017. Google Scholar
  24. Orit E. Raz, Micha Sharir, and József Solymosi. Polynomials vanishing on grids: The Elekes-Rónyai problem revisited. American Journal of Mathematics, 138(4):1029-1065, 2016. Google Scholar
  25. Orit E. Raz, Micha Sharir, and Frank De Zeeuw. Polynomials vanishing on Cartesian products: The Elekes-Szabó theorem revisited. Duke Mathematical Journal, 165(18):3517-3566, 2016. Google Scholar
  26. David Alan Rosenthal. The classification of the order indiscernibles of real closed fields and other theories. PhD thesis, University of Wisconsin–Madison, 1981. Google Scholar
  27. Tomasz Schoen and Ilya D. Shkredov. On Sumsets of Convex Sets. Combinatorics, Probability and Computing, 20(5):793-798, 2011. Google Scholar
  28. Ryan Schwartz, József Solymosi, and Frank de Zeeuw. Extensions of a result of Elekes and Rónyai. Journal of Combinatorial Theory, Series A, 120(7):1695-1713, 2013. Google Scholar
  29. Andrew Suk. On the Erdős-Szekeres convex polygon problem. Journal of the American Mathematical Society, 30:1047-1053, 2017. Google Scholar
  30. Pavel Valtr. Sets in ℝ^d with no large empty convex subsets. Discrete Mathematics, 108(1-3):115-124, 1992. Google Scholar
  31. Eric W. Weisstein. No-Three-in-a-Line-Problem. online, 2005. Available from: URL: http://mathworld.wolfram.com/No-Three-in-a-Line-Problem.html.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact