Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Four-Connected Triangulations of Planar Point Sets

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

In this paper, we consider the problem of determining in polynomial time whether a given planar point set \(P\) of \(n\) points in general position admits a 4-connected triangulation. We propose a necessary and sufficient condition for recognizing such point sets \(P\), and present an \(O(n^3)\) time algorithm for constructing a 4-connected triangulation of \(P\), if it exists. Thus, our algorithm solves a longstanding open problem in computational geometry and geometric graph theory. We also provide a simple \(O(n^2)\) time method for constructing a non-complex triangulation of \(P\), if it exists. This method provides a new insight into the structure of 4-connected triangulations of point sets.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26
Fig. 27
Fig. 28
Fig. 29
Fig. 30
Fig. 31
Fig. 32

Similar content being viewed by others

References

  1. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. North Holland, New York (1985)

    Google Scholar 

  2. Chazelle, B.: On the convex layers of a planar set. IEEE Trans. Inf. Theory 4, 509–517 (1985)

    Article  MathSciNet  Google Scholar 

  3. de Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry, Algorithms and Applications, 3rd edn. Springer, Berlin (2008)

    MATH  Google Scholar 

  4. Dey, T.K., Dillencourt, M.B., Ghosh, S.K., Cahill, J.M.: Triangulating with high connectivity. Comput. Geom. 8, 39–56 (1995)

    Article  MathSciNet  Google Scholar 

  5. Diwan, A.A., Ghosh, S.K., Roy, B.: Four-connected triangulations of planar point sets (2013). http://arxiv.org/abs/1310.1726v1

  6. García, A., Hurtado, F., Huemer, C., Tejel, J., Valtr, P.: On triconnected and cubic plane graphs on given point sets. Comput. Geom. 42(9), 913–922 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  7. Ghosh, S.K., Roy, B.: Problems on plane triangulations of points. In: Proceedings of the India-Taiwan Conference on Discrete Mathematics, Hsinchu, Taiwan, pp. 57–60 (2013)

  8. Hurtado, F., Toth, C.D.: Plane geometric graph augmentation: a generic perspective. Thirty Essays on Geometric Graph Theory, pp. 327–354. Springer, New York (2013)

    Chapter  Google Scholar 

  9. Laumond, J.-P.: Connectivity of plane triangulations. Inf. Process. Lett. 34, 87–96 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  10. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1990)

    Google Scholar 

Download references

Acknowledgments

The authors would like to thank reviewers for their helpful comments and suggestions on the paper. The first version of this paper [5] was reported on October 7, 2013.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai, 400076, India

    Ajit Arvind Diwan

  2. School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, 400005, India

    Subir Kumar Ghosh & Bodhayan Roy

Authors
  1. Ajit Arvind Diwan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Subir Kumar Ghosh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bodhayan Roy
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Subir Kumar Ghosh.

Additional information

Editor in charge: János Pach.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Diwan, A.A., Ghosh, S.K. & Roy, B. Four-Connected Triangulations of Planar Point Sets. Discrete Comput Geom 53, 713–746 (2015). https://doi.org/10.1007/s00454-015-9694-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-015-9694-x

Keywords

Search

Navigation