More Web Proxy on the site http://driver.im/

research-article

On degrees in random triangulations of point sets

Authors:

Emo WelzlAuthors Info & Claims

SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

Pages 297 - 306

https://doi.org/10.1145/1810959.1811009

Published: 13 June 2010 Publication History

Abstract

We study the expected number of interior vertices of degree i in a triangulation of a point set S, drawn uniformly at random from the set of all triangulations of S, and derive various bounds and inequalities for these expected values. One of our main results is: For any set S of N points in general position, and for any fixed i, the expected number of vertices of degree i in a random triangulation is at least γiN, for some fixed positive constant γi (assuming that N > i and that at least some fixed fraction of the points are interior).

We also present a new application for these expected values, using upper bounds on the expected number of interior vertices of degree 3 to get a new lower bound, Ω(2.4317^N), for the minimal number of triangulations any N-element planar point set in general position must have. This improves the previously best known lower bound of Ω(2.33^N).

References

[1]

M. Ajtai, V. Chvatal, M. M. Newborn, and E. Szemeredi, Crossing-free subgraphs, Annals Discrete Math. 12 (1982), 9--12.

[2]

O. Aichholzer, F. Hurtado, and M. Noy, A lower bound on the number of triangulations of planar point sets, Comput. Geom. Theory Appl. 29(2) (2004), 135--145.

Digital Library

[3]

M.O. Denny and C.A. Sohler, Encoding a triangulation as a permutation of its point set, Proc. 9th Canadian Conf. on Computational Geometry (1997), 39--43.

[4]

O. Gimenez and M. Noy, The number of planar graphs and properties of random planar graphs, Proc. International Conf. on Analysis of Algorithms, Discrete Math. & Theoretical Computer Sci. AD (2005), 147--156.

[5]

F. Hurtado, M. Noy, Counting triangulations of almost-convex polygons, Ars Combin. 45 (1997), 169--179.

[6]

V. A. Liskovets, A pattern of asymptotic vertex valency distributions in planar maps, J. Combinat. Theory, Ser. B 75 (1999), 116--133.

Digital Library

[7]

P. McCabe and R. Seidel, New lower bounds for the number of straight-edge triangulations of a planar point set, Proc. 20th European Workshop Comput. Geom. (2004).

[8]

C. McDiarmid, A. Steger, and D.J.A. Welsh, Random planar graphs, J. Combinat. Theory, Ser. B 93 (2005), 187--205.

Digital Library

[9]

A. Razen, J. Snoeyink, E. Welzl, Number of crossing-free geometric graphs vs. triangulations, Electronic Notes in Discrete Math. 31 (2008), 195--200.

[10]

F. Santos and R. Seidel, A better upper bound on the number of triangulations of a planar point set, J. Combinat. Theory, Ser. A 102(1) (2003), 186--193.

Digital Library

[11]

R. Seidel, On the number of triangulations of planar point sets, Combinatorica 18(2) (1998), 297--299.

[12]

M. Sharir and A. Sheffer, Counting triangulations of planar point sets, 0911.3352v2 (improves {13}).

[13]

M. Sharir and E. Welzl, Random triangulations of planar point sets, Proc. 22nd ACM Symp. on Computational Geometry (2006), 273--281.

Digital Library

[14]

W. S. Smith, Studies in Computational Geometry Motivated by Mesh Generation, Ph.D. Thesis, Princeton University, 1989.

Digital Library

[15]

R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

Cited By

Wettstein MCheng SDevillers O(2014)Counting and Enumerating Crossing-free Geometric GraphsProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582145(1-10)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582145
Alvarez VBringmann KCurticapean RRay SDey TWhitesides S(2012)Counting crossing-free structuresProceedings of the twenty-eighth annual symposium on Computational geometry10.1145/2261250.2261259(61-68)Online publication date: 17-Jun-2012
https://dl.acm.org/doi/10.1145/2261250.2261259

Index Terms

On degrees in random triangulations of point sets
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Enumeration

Recommendations

Random triangulations of planar point sets
SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

Let S be a finite set of n+3 points in general position in the plane, with 3 extreme points and n interior points. We consider triangulations drawn uniformly at random from the set of all triangulations of S, and investigate the expected number, v_i, of ...
On degrees in random triangulations of point sets

We study the expected number of interior vertices of degree i in a triangulation of a planar point set S, drawn uniformly at random from the set of all triangulations of S, and derive various bounds and inequalities for these expected values. One of our ...
Efficient generation of triconnected plane triangulations

A "rooted" plane triangulation is a plane triangulation with one designated vertex on the outer face. A simple algorithm to generate all triconnected rooted plane triangulations with at most n vertices is presented. The algorithm uses O(n) space and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

June 2010

452 pages

ISBN:9781450300162

DOI:10.1145/1810959

Program Chairs:
David Kirkpatrick
University of British Columbia, Canada
,
Joseph Mitchell
SUNY Stony Brook, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '10

Sponsor:

SoCG '10: Symposium on Computational Geometry

June 13 - 16, 2010

Utah, Snowbird, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
106
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wettstein MCheng SDevillers O(2014)Counting and Enumerating Crossing-free Geometric GraphsProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582145(1-10)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582145
Alvarez VBringmann KCurticapean RRay SDey TWhitesides S(2012)Counting crossing-free structuresProceedings of the twenty-eighth annual symposium on Computational geometry10.1145/2261250.2261259(61-68)Online publication date: 17-Jun-2012
https://dl.acm.org/doi/10.1145/2261250.2261259

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten