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
An Optimal Algorithm for Finding the Kernel of a Polygon
Full text PdfPdf (412 KB)
Source Journal of the ACM (JACM) archive
Volume 26 ,  Issue 3  (July 1979) table of contents
Pages: 415 - 421  
Year of Publication: 1979
ISSN:0004-5411
Authors
D. T. Lee  Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL and University of Illinois at Urbana-Champaign, Urbana, Illinois
F. P. Preparata  Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 9,   Downloads (12 Months): 133,   Citation Count: 15
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/322139.322142
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
SHAMOS, M I, AND HOEY, D Geometric intersection problems 17th Annual Syrup on Foundattons of Computer Science, Houston, Tex, Oct 1976, pp 208-215 (IEEE)

CITED BY  15
Christian Icking , Rolf Klein, Searching for the kernel of a polygon—a competitive strategy, Proceedings of the eleventh annual symposium on Computational geometry, p.258-266, June 05-07, 1995, Vancouver, British Columbia, Canada
Mark H. Overmars , Jan van Leeuwen, Dynamically maintaining configurations in the plane (Detailed Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.135-145, April 28-30, 1980, Los Angeles, California, United States
A. Fournier , D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics (TOG), v.3 n.2, p.153-174, April 1984
Danny Z. Chen, An optimal parallel algorithm for detecting weak visibility of a simple polygon, Proceedings of the eighth annual symposium on Computational geometry, p.63-72, June 10-12, 1992, Berlin, Germany
Joseph O'Rourke, An on-line algorithm for fitting straight lines between data ranges, Communications of the ACM, v.24 n.9, p.574-578, Sept. 1981
Gautam Das , Giri Narasimhan, Optimal linear-time algorithm for the shortest illuminating line segment in a polygon, Proceedings of the tenth annual symposium on Computational geometry, p.259-266, June 06-08, 1994, Stony Brook, New York, United States
R. Cole , M. T. Goodrich, Optimal parallel algorithms for polygon and point-set problems, Proceedings of the fourth annual symposium on Computational geometry, p.201-210, June 06-08, 1988, Urbana-Champaign, Illinois, United States
Binay K. Bhattacharya , Gautam Das , Asish Mukhopadhyay , Giri Narasimhan, Optimally computing a shortest weakly visible line segment inside a simple polygon, Computational Geometry: Theory and Applications, v.23 n.1, p.1-29, July 2002
Danny Z. Chen , Mikhail J. Atallah, Optimal Parallel Hypercube Algorithms for Polygon Problems, IEEE Transactions on Computers, v.44 n.7, p.914-922, July 1995
Sven Schuierer, An O(log log n) time algorithm to compute the kernel of a polygon, Nordic Journal of Computing, v.1 n.4, p.458-474, Winter 1994
Alejandro López-Ortiz , Sven Schuierer, Searching and on-line recognition of star-shaped polygons, Information and Computation, v.185 n.1, p.66-88, August 25, 2003
Bor-Kuan Lu , Fang-Rong Hsu , Chuan Yi Tang, Finding the shortest boundary guard of a simple polygon, Theoretical Computer Science, v.263 n.1-2, p.113-121, July 28 2001
Danny Z. Chen, Efficient Geometric Algorithms on the EREW PRAM, IEEE Transactions on Parallel and Distributed Systems, v.6 n.1, p.41-47, January 1995
Gautam Das , Paul J. Heffernan , Giri Narasimhan, Finding all weakly-visible chords of a polygon in linear time, Nordic Journal of Computing, v.1 n.4, p.433-457, Winter 1994
J.-R. Sack , S. Suri, An Optimal Algorithm for Detecting Weak Visibility of a Polygon, IEEE Transactions on Computers, v.39 n.10, p.1213-1219, October 1990

INDEX TERMS

Primary 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

Additional 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


General Terms:
Algorithms, Design, Performance, Reliability, Theory, Verification

Collaborative Colleagues:
D. T. Lee: colleagues
F. P. Preparata: 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