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
On computing simple circuits on a set of line segments
Full text PdfPdf (631 KB)
Source Annual Symposium on Computational Geometry archive
Proceedings of the second annual symposium on Computational geometry table of contents
Yorktown Heights, New York, United States
Pages: 52 - 60  
Year of Publication: 1986
ISBN:0-89791-194-6
Authors
D Rappaport  School of Computer Science, McGill University, 805 Sherbrooke St., W. Montreal, Canada H3A 2K6
H Imai  Department of Mathematical Engineering and Instrumentation Physics, University of Tokyo, Bunkyo-Ku, Tokyo, Japan
G T Toussaint  School of Computer Science, McGill University, 805 Sherbrooke St., W. Montreal, Canada H3A 2K6
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): 3,   Downloads (12 Months): 9,   Citation Count: 2
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/10515.10521
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.

 
Bentley and Ottmann
Bentley, J. L., and T. A. Ottmann,"Algorithms for Reporting and Counting Geometric Intersections", IEEE Transactions on Computers, vol. c-28 No. 9, (1979), 643-647.
 
Graham
Graham, R. L., "An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set", Information Processing Letters, vol. l, (1072), 132- 133.
 
Hopcroft and Karp
Hopcroft, J. E., and R. M. Karp, "An n6/2 Algorithm for Maximum Matchings in Bipartite Graphs", SIAM Journal on Computing, vol. 2 (1973), 225- 231.
 
Rappaport
Rappaport, David, "Computing Simple Circuits on a Set of Line Segments is NP-Complete" Technical Report No. SOCS-86.6 MeGill University 1986.
 
Shamos and Hoey
Shamos, M. I. and D. Hoey, "Geometric Intersection Problems", Proceedings of the 17th FOCS, Oct. 1976, 208- 215.
 
Toussaint
Toussaint, G. T., "A Historical Note on Convex Hull Finding Algorithms", Technical Report No. SOCS-83.14 McGill University (1983).
 
Suri
Suri, Subhash, Personal communication.

CITED BY  2
P. D. Alevizos , J. Boissonnat , M. Yvinec, An optimal O(n log n) algorithm for contour reconstruction from rays, Proceedings of the third annual symposium on Computational geometry, p.162-170, June 08-10, 1987, Waterloo, Ontario, Canada
D. Rappaport, Computing simple circuits from a set of line segments is NP-complete, Proceedings of the third annual symposium on Computational geometry, p.322-330, June 08-10, 1987, Waterloo, Ontario, Canada

INDEX TERMS

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS


General Terms:
Algorithms, Theory, Verification

Collaborative Colleagues:
D Rappaport: colleagues
H Imai: colleagues
G T Toussaint: 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