Deterministic algorithms for 3-D diameter and some 2-D lower envelopes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deterministic algorithms for 3-D diameter and some 2-D lower envelopes

Full text

Pdf (962 KB)

Source

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

Clear Water Bay, Kowloon, Hong Kong

Pages: 290 - 299

Year of Publication: 2000

ISBN:1-58113-224-7

Author

Edgar A. Ramos

Max-Planck-Institut für Informatik, Saarbrücken, Germany

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): 6, Downloads (12 Months): 33, Citation Count: 2

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/336154.336215 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	Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, v.6 n.5, p.407-422, 1991 [doi>10.1007/BF02574698]
	2	P. K. Agarwal and J. Matougek. On range searching with semialgebraic sets. Discrete Comput. Geom. 11 (1994), 393-418.
	3	Pankaj K. Agarwal , Otfried Schwarzkopf , Micha Sharir, The overlay of lower envelopes in three dimensions and its applications, Proceedings of the eleventh annual symposium on Computational geometry, p.182-189, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220299]
	4	N. M. Amato, M. T. Goodrich, and E. A. Ramos. Parallel algorithms for higher-dimensional convex hulls. In Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 94), 683-694, 1994.
	5	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 [doi>10.1145/225058.225285]
	6	Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Computing the arrangement of curve segments: divide-and-conquer algorithms via sampling, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.705-706, January 09-11, 2000, San Francisco, California, United States
	7	Nancy M. Amato , Edgar A. Ramos, On computing Voronoi diagrams by divide-prune-and-conquer, Proceedings of the twelfth annual symposium on Computational geometry, p.166-175, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237347]
	8	Sergei N. Bespamyatnikh, An efficient algorithm for the three-dimensional diameter problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.137-146, January 25-27, 1998, San Francisco, California, United States
	9	H. Br6nnimann, B. Chazelle, and J. Matou~ek. Product range spaces, sensitive sampling, and derandomization. In Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 93), 400-409, 1993.
	10	Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
	11	B. Chazelle, H. Edelsbrunner, L. Guibas and M. Sharir, Diameter, width, closest line pair, and parametric searching, Discrete Comput. Geom. 10 (1993), 183-196.
	12	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]
	13	Frank Dehne , Xiaotie Deng , Patrick Dymond , Andreas Fabri , Ashfaq A. Khokhar, A randomized parallel 3D convex hull algorithm for coarse grained multicomputers, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.27-33, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215410]
	14	X. Deng and B. Zhu. A randomized algorithm for the Voronoi diagram of line segments on coarse grained multiprocessors. Algorithmica 24 (1999), 270-286.
	15	D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection. Theoret. Comput. Sci. 27 (1983), 241-253.
	16	Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
	17	Michael T. Goodrich, Planar separators and parallel polygon triangulation, Journal of Computer and System Sciences, v.51 n.3, p.374-389, Dec. 1995 [doi>10.1006/jcss.1995.1076]
	18	D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2 (1987), 127-151.
	19	A. Heppes, Beweis einer Vermutung von A. V~zsonyi, Acta Math. Acad. Sci. Hungar. 7 (1956), 463-466.
	20	U. Kfihn. Lokale Eigenschaften in der algorithmischen Geometrie mit Anwendungen in der Parallelverarbeitung. Inaugural-Dissertation, Fachbereich Mathematik und Informatik, Westf/ilische Wilhelms-Universit~t Mfinster. 1998.
	21	R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Comput. 3{} (1979), 177-189.
	22	Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Journal of Computer and System Sciences, v.50 n.2, p.203-208, April 1995
	23	Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
	24	Jiří Matoušek, Derandomization in computational geometry, Journal of Algorithms, v.20 n.3, p.545-580, May 1996 [doi>10.1006/jagm.1996.0027]
	25	Jiří Matoušek , Otfried Schwarzkopf, A deterministic algorithm for the three-dimensional diameter problem, Computational Geometry: Theory and Applications, v.6 n.4, p.253-262, July 1996 [doi>10.1016/0925-7721(95)00025-9]
	26	K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
	27	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	28	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	29	Edgar A. Ramos, An algorithm for intersecting equal radius balls in R\u3\d, University of Illinois at Urbana-Champaign, Champaign, IL, 1994
	30	Edgar A. Ramos, Construction of 1-d lower envelopes and applications, Proceedings of the thirteenth annual symposium on Computational geometry, p.57-66, June 04-06, 1997, Nice, France [doi>10.1145/262839.262864]
	31	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
	32	A. C. Yao. On constructing minimum spanning trees in k-dimensional space and related problems. SIAM J. Cornput. 11 (1982), 721-736.
	33	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]
	34	Chee-Keng Yap, A geometric consistency theorem for a symbolic perturbation scheme, Journal of Computer and System Sciences, v.40 n.1, p.2-18, February 1990 [doi>10.1016/0022-0000(90)90016-E]

CITED BY 2

	Sariel Har-Peled, A practical approach for computing the diameter of a point set, Proceedings of the seventeenth annual symposium on Computational geometry, p.177-186, June 2001, Medford, Massachusetts, United States
	Otfried Cheong , Chan-Su Shin , Antoine Vigneron, Computing farthest neighbors on a convex polytope, Theoretical Computer Science, v.296 n.1, p.47-58, 4 March 2003