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 deterministic algorithm for the three-dimensional diameter problem
Full text PdfPdf (736 KB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents
San Diego, California, United States
Pages: 478 - 484  
Year of Publication: 1993
ISBN:0-89791-591-7
Authors
Jiří Matoušek
Otfried Schwarzkopf
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 3,   Downloads (12 Months): 9,   Citation Count: 4
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/167088.167217
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.

 
Cha92
B. Chazelle. Cutting hyperplanes for divideand-conquer. Dzscrete # Computational Geometry, 1992. To appear. Preliminary version: Proc. 32nd IEEE Symposzum on Foundalzons of Computer Science (1991).
CEGS92
Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, Diameter, width, closest line pair, and parametric searching, Proceedings of the eighth annual symposium on Computational geometry, p.120-129, June 10-12, 1992, Berlin, Germany  [doi>10.1145/142675.142702]
 
CF90
B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinalomca, 10:229-249, 1990.
 
CS89
K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989  [doi>10.1007/BF02187740]
Dye92
Martin Dyer, A class of convex programs with applications to computational geometry, Proceedings of the eighth annual symposium on Computational geometry, p.9-15, June 10-12, 1992, Berlin, Germany  [doi>10.1145/142675.142681]
 
Mat91
Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991  [doi>10.1007/BF02574697]
Mat91a
Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States  [doi>10.1145/103418.103470]
 
Mat92
Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992  [doi>10.1007/BF02293051]
Meg83
Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983  [doi>10.1145/2157.322410]
 
Ren92
James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Part III: quantifier elimination, Journal of Symbolic Computation, v.13 n.3, p.329-352, March 1992
YY85
A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States  [doi>10.1145/22145.22163]

CITED BY  4
Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Computing faces in segment and simplex arrangements, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.672-682, May 29-June 01, 1995, Las Vegas, Nevada, United States
Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
Daniele V. Finocchiaro , Marco Pellegrini, On computing the diameter of a point set in high dimensional Euclidean space, Theoretical Computer Science, v.287 n.2, p.501-514, 28 September 2002
David Fernández-Baca , Giora Slutzki , David Eppstein, Using sparsification for parametric minimum spanning tree problems, Nordic Journal of Computing, v.3 n.4, p.352-366, Winter 1996

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.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching


General Terms:
Algorithms, Theory, Verification

Collaborative Colleagues:
Jiří Matoušek: colleagues
Otfried Schwarzkopf: 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