ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
A (usually?) connected subgraph of the minimum weight triangulation
Full text PdfPdf (892 KB)
Source Annual Symposium on Computational Geometry archive
Proceedings of the twelfth annual symposium on Computational geometry table of contents
Philadelphia, Pennsylvania, United States
Pages: 204 - 213  
Year of Publication: 1996
ISBN:0-89791-804-5
Authors
Matthew T. Dickerson  Middlebury College, Middlebury VT
Mark H. Montague  Middlebury College, Middlebury VT and now at Dartmouth College, Hanover NH
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): 30,   Downloads (12 Months): 69,   Citation Count: 6
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/237218.237364
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
Oswin Aichholzer , Günter Rote, Triangulations intersect nicely, Proceedings of the eleventh annual symposium on Computational geometry, p.220-229, June 05-07, 1995, Vancouver, British Columbia, Canada  [doi>10.1145/220279.220303]
 
2
S. Cheng and Y.Xu, "Approaching the Largest /?-skeleton Within the Minimum Weight Triangulation.'' manuscript (1995)
 
3
S. Cheng, M.Golin and J.Tsang "Expected Case Analysis of /~-skeletons with Applications to the Construction of Minimum Weight Triangulations.'' CCCG Conf. Proc., Quebec City, 1995 279-284.
 
4
Norishige Chiba , Takao Nishizeki, Arboricity and subgraph listing algorithms, SIAM Journal on Computing, v.14 n.1, p.210-223, Feb. 1985  [doi>10.1137/0214017]
 
5
G. Das , D. Joseph, Which triangulations approximate the complete graph?, Proceedings of the international symposium on Optimal algorithms, p.168-192, November 1989, Varna, Bulgaria
 
6
Matthew T. Dickerson , Robert L. Scot Drysdale , Scott A. McElfresh , Emo Welzl, Fast greedy triangulation algorithms, Computational Geometry: Theory and Applications, v.8 n.2, p.67-86, July 1997  [doi>10.1016/S0925-7721(97)89149-3]
7
Matthew T. Dickerson , Scott A. McElfresh , Mark Montague, New algorithms and empirical findings on minimum weight triangulation heuristics (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.238-247, June 05-07, 1995, Vancouver, British Columbia, Canada  [doi>10.1145/220279.220305]
 
8
David Eppstein , Mark Overmars , Günter Rote , Gerhard Woeginger, Finding minimum area k-gons, Discrete & Computational Geometry, v.7 n.1, p.45-58, 1992  [doi>10.1007/BF02187823]
 
9
Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
 
10
P. D. Gilbert, "New results in planar triangulations.'' Report R-850, University of illinois Coordinated Science Lab. (1979).
 
11
J. Mark Keil, Computing a subgraph of the minimum weight triangulation, Computational Geometry: Theory and Applications, v.4 n.1, p.13-26, May 1994
 
12
G. Klincsek, "Minimal triangulations of polygonal domains." Ann. Discrete Math. 9 (1980) 121- 123.
 
13
Scott McElfresh. St. Lawrence University. Personal communication. Work in progress.
 
14
Bo-Ting Yang , Yin-Feng Xu , Zhao-yong You, A Chain Decomposition Algorithm for the Proof of a Property on Minimum Weight Triangulations, Proceedings of the 5th International Symposium on Algorithms and Computation, p.423-427, August 25-27, 1994

CITED BY  6
Ronald Beirouti , Jack Snoeyink, Implementations of the LMT heuristic for minimum weight triangulation, Proceedings of the fourteenth annual symposium on Computational geometry, p.96-105, June 07-10, 1998, Minneapolis, Minnesota, United States
Christos Levcopoulos , Drago Krznaric, A near-optimal heuristic for minimum weight triangulation of convex polygons, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.518-527, January 05-07, 1997, New Orleans, Louisiana, United States
Nina Amenta , Marshall Bern , David Eppstein, Optimal point placement for mesh smoothing, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.528-537, January 05-07, 1997, New Orleans, Louisiana, United States
William Lenhart , Giuseppe Liotta, The drawability problem for minimum weight triangulations, Theoretical Computer Science, v.270 n.1-2, p.261-286, January
Michael Hoffmann , Yoshio Okamoto, The minimum weight triangulation problem with few inner points, Computational Geometry: Theory and Applications, v.34 n.3, p.149-158, July 2006
Cao An Wang , Yin-Feng Xu, Computing a Minimum Weight Triangulation of a Sparse Point Set, Journal of Global Optimization, v.15 n.1, p.73-83, July 1999

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms


General Terms:
Algorithms, Experimentation, Theory, Verification

Collaborative Colleagues:
Matthew T. Dickerson: colleagues
Mark H. Montague: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player