Pseudo-triangulations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pseudo-triangulations: theory and applications

Full text

Pdf (1.04 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twelfth annual symposium on Computational geometry table of contents

Philadelphia, Pennsylvania, United States

Pages: 291 - 300

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Michel Pocchiola	Departement de Mathématiques et Informatique, Ecole normale supérieure, ura 1327 du Cnrs, 45 rue d'Ulm 75230 Paris Cedex 05, France
Gert Vegter	Dept. of Math. and Comp. Sc., University of Groningen, P. O. Box 800, 9700 AV Groningen, The Netherlands

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 16, Citation Count: 12

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237218.237398 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Michel Pocchiola , Gert Vegter, The visibility complex, Proceedings of the ninth annual symposium on Computational geometry, p.328-337, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161159]
	2	Michel Pocchiola , Gert Vegter, Computing the visibility graph via pseudo-triangulations, Proceedings of the eleventh annual symposium on Computational geometry, p.248-257, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220306]
	3	Mark de Berg, Ray Shooting, Depth Orders and Hidden Surface Removal, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
	4	B. Chazelle. Computational geometry: a retrospective, volume i of Lecture Notes Series on Computing, pages 22-46. World Scientific, 2 edition, 1995.
	5	L. Fejes T6th. Illumination of convex discs. Acts Math. Acad. Sci. Hungar., 29(3-4):355-360, 1977.
	6	H. Edelsbrunner , A. D. Robison , Xiao-Jun Shen, Covering convex sets with non-overlapping polygons, Discrete Mathematics, v.81 n.2, p.153-164, April 1990 [doi>10.1016/0012-365X(90)90147-A]
	7	A. BjSrner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler. Oriented Matroids. Encyclopedia of Mathematics and Applications. Cambridge University Press, 1993.
	8	J. Richter-Gebert and G. M. Ziegler. Realization spaces of 4-polytopes are universal. Bulletin of the American Mathematical Society, 32(4), October 1995.
	9	J. Pach and P. K. Agarwal. Combinatorial Geometry. John Wiley & Sons, New York, NY, 1995.
	10	J.E_ Cloo~tm~ ~d R. Poll~zk. Multldlm~a~lonal SorOng. Siam J. Comput., 12:484-507, 1983.
	11	E. A. Bender, E. R. Candfield, and B. D. McKay. The asymptotic number of labeled connected graphs with a given number of vertices and edges. Random Structures and Algorithms, 1(2):127-169, 1990.

CITED BY 12

	Pierre Angelier , Michel Pocchiola, A sum of squares theorem for visibility, Proceedings of the seventeenth annual symposium on Computational geometry, p.302-311, June 2001, Medford, Massachusetts, United States
	Ruth Haas , David Orden , Günter Rote , Francisco Santos , Brigitte Servatius , Hermann Servatius , Diane Souvaine , Ileana Streinu , Walter Whiteley, Planar minimally rigid graphs and pseudo-triangulations, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Joseph O'Rourke, Computational geometry column 43, ACM SIGACT News, v.33 n.1, March 2002
	Vladlen Koltun, Segment intersection searching problems in general settings, Proceedings of the seventeenth annual symposium on Computational geometry, p.197-206, June 2001, Medford, Massachusetts, United States
	Ruth Haas , David Orden , Günter Rote , Francisco Santos , Brigitte Servatius , Herman Servatius , Diane Souvaine , Ileana Streinu , Walter Whiteley, Planar minimally rigid graphs and pseudo-triangulations, Computational Geometry: Theory and Applications, v.31 n.1-2, p.31-61, May 2005
	David Orden , Francisco Santos, The polytope of non-crossing graphs on a planar point set, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.250-257, July 04-07, 2004, Santander, Spain
	Julien Basch , Jeff Erickson , Leonidas J. Guibas , John Hershberger , Li Zhang, Kinetic collision detection between two simple polygons, Computational Geometry: Theory and Applications, v.27 n.3, p.211-235, March 2004
	Sergey Bereg, Transforming pseudo-triangulations, Information Processing Letters, v.90 n.3, p.141-145, 16 May 2004
	Bettina Speckmann , Csaba D. Tóth, Allocating vertex π-guards in simple polygons via pseudo-triangulations, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Sergey Bereg, Enumerating pseudo-triangulations in the plane, Computational Geometry: Theory and Applications, v.30 n.3, p.207-222, March 2005
	Günter Rote, Pseudotriangulations, polytopes, and how to expand linkages, Proceedings of the eighteenth annual symposium on Computational geometry, p.133-134, June 05-07, 2002, Barcelona, Spain
	Joachim Gudmundsson , Christos Levcopoulos, Minimum weight pseudo-triangulations, Computational Geometry: Theory and Applications, v.38 n.3, p.139-153, October, 2007