Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-25T17:40:08.199Z Has data issue: false hasContentIssue false
  • English
  • Français

Convex Polygons in Geometric Triangulations†

Part of: Extremal combinatorics General convexity Graph theory Algorithms - Computer Science

Published online by Cambridge University Press:  30 May 2017

ADRIAN DUMITRESCU  and
CSABA D. TÓTH
ADRIAN DUMITRESCU
Affiliation:
Department of Computer Science, University of Wisconsin–Milwaukee, USA (e-mail: [email protected])
CSABA D. TÓTH
Affiliation:
Department of Mathematics, California State University Northridge, Los Angeles, CA, USA Department of Computer Science, Tufts University, Medford, MA, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that the maximum number of convex polygons in a triangulation of n points in the plane is O(1.5029n). This improves an earlier bound of O(1.6181n) established by van Kreveld, Löffler and Pach (2012), and almost matches the current best lower bound of Ω(1.5028n) due to the same authors. Given a planar straight-line graph G with n vertices, we also show how to compute efficiently the number of convex polygons in G.

MSC classification

Primary: 05C85: Graph algorithms
Secondary: 05D99: None of the above, but in this section 52A10: Convex sets in $2$ dimensions (including convex curves) 68W05: Nonnumerical algorithms
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 5 , September 2017 , pp. 641 - 659
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

An extended abstract of this paper appeared in the Proceedings of the 29th International Symposium on Algorithms and Data Structures (WADS 2015), Vol. 9214 of Lecture Notes in Computer Science, Springer, 2015, pp. 289–300.

References

[1] Aichholzer, O., Hackl, T., Vogtenhuber, B., Huemer, C. Hurtado, F. and Krasser, H. (2007) On the number of plane geometric graphs. Graphs Combin. 23 67–84.Google Scholar
[2] Ajtai, M., Chvátal, V., Newborn, M. and Szemerédi, E. (1982) Crossing-free subgraphs. Ann. Discrete Math. 12 9–12.Google Scholar
[3] Alvarez, V., Bringmann, K., Ray, S. and Seidel, R. (2015) Counting triangulations and other crossing-free structures approximately. Comput. Geom. Theory Appl. 48 386–397.Google Scholar
[4] Alvarez, V. and Seidel, R. (2013) A simple aggregative algorithm for counting triangulations of planar point sets and related problems. In Proc. 29th Symposium on Computational Geometry (SoCG), ACM Press, pp. 1–8.Google Scholar
[5] Aronov, B., van Kreveld, M., Löffler, M. and Silveira, R. I. (2011) Peeling meshed potatoes. Algorithmica 60 349–367.Google Scholar
[6] Buchin, K., Knauer, C., Kriegel, K., Schulz, A. and Seidel, R. (2007) On the number of cycles in planar graphs. In Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON), Vol. 4598 of Lecture Notes in Computer Science, Springer, pp. 97–107.CrossRefGoogle Scholar
[7] Chang, J. S. and Yap, C. K. (1986) A polynomial solution for the potato-peeling problem. Discrete Comput. Geom. 1 155–182.Google Scholar
[8] Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009) Introduction to Algorithms, third edition, MIT Press.Google Scholar
[9] Dumitrescu, A., Löffler, M., Schulz, A. and Tóth, C. D. (2016) Counting carambolas. Graphs Combin. 32 923–942.Google Scholar
[10] Dumitrescu, A., Mandal, R. and Tóth, C. D. (2016) Monotone paths in geometric triangulations. arXiv:1608.04812. Extended abstract of an earlier version in Proc. 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), Vol. 9843 of Lecture Notes in Computer Science, Springer, pp. 411–422.Google Scholar
[11] Dumitrescu, A., Schulz, A., Sheffer, A. and Tóth, C. D. (2013) Bounds on the maximum multiplicity of some common geometric graphs. SIAM J. Discrete Math. 27 802–826.CrossRefGoogle Scholar
[12] Dumitrescu, A. and Tóth, C. D. (2012) Computational Geometry Column 54. SIGACT News Bull. 43 90–97.Google Scholar
[13] Dumitrescu, A. and Tóth, C. D. (2017) Convex polygons in geometric triangulations. arXiv:1411.1303v3 Google Scholar
[14] Eppstein, D., Overmars, M., Rote, G. and Woeginger, G. (1992) Finding minimum area k-gons. Discrete Comput. Geom. 7 45–58.CrossRefGoogle Scholar
[15] Erdős, P. (1978) Some more problems on elementary geometry. Gazette Austral. Math. Soc. 5 52–54.Google Scholar
[16] Erdős, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Compositio Math. 2 463–470.Google Scholar
[17] García, A., Noy, M. and Tejel, A. (2000) Lower bounds on the number of crossing-free subgraphs of K N . Comput. Geom. Theory Appl. 16 211–221.Google Scholar
[18] Goodman, J. E. (1981) On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato. Geometria Dedicata 11 99–106.Google Scholar
[19] van Kreveld, M. J., Löffler, M. and Pach, J. (2012) How many potatoes are in a mesh? In Proc. 23rd International Symposium on Algebraic Computation (ISAAC), Vol. 7676 of Lecture Notes in Computer Science, Springer, pp. 166–176.Google Scholar
[20] Marx, D. and Miltzow, T. (2016) Peeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problems. In Proc. 32nd International Symposium on Computational Geometry (SoCG), LIPIcs 51, Schloss Dagstuhl, article 52.Google Scholar
[21] Morris, W. and Soltan, V. (2000) The Erdős–Szekeres problem on points in convex position: A survey. Bull. Amer. Math. Soc. 37 437–458.Google Scholar
[22] Razen, A., Snoeyink, J. and Welzl, E. (2008) Number of crossing-free geometric graphs vs. triangulations. Electron. Notes Discrete Math. 31 195–200.CrossRefGoogle Scholar
[23] Razen, A. and Welzl, E. (2011) Counting plane graphs with exponential speed-up. In Rainbow of Computer Science Calude, C. S. et al., eds), Springer, pp. 36–46.CrossRefGoogle Scholar
[24] Sharir, M. and Sheffer, A. (2011) Counting triangulations of planar point sets. Electron. J. Combin. 18 P70.Google Scholar
[25] Sharir, M. and Sheffer, A. (2013) Counting plane graphs: Cross-graph charging schemes. Combin. Probab. Comput. 22 935–954.Google Scholar
[26] Sharir, M., Sheffer, A. and Welzl, E. (2013) Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn's technique. J. Combin. Theory Ser. A 120 777–794.Google Scholar
[27] Sharir, M. and Welzl, E. (2006) On the number of crossing-free matchings, cycles, and partitions. SIAM J. Comput. 36 695–720.Google Scholar
[28] Sheffer, A. (2015) Numbers of plane graphs. https://adamsheffer.wordpress.com/numbers-of-plane-graphs/ Google Scholar
[29] Wettstein, M. (2016) Counting and enumerating crossing-free geometric graphs. In Proc. 30th Symposium on Computational Geometry (SOCG), ACM Press, pp. 1–10. Full paper available at arXiv:1604.05350.Google Scholar