Construction of 1-d lower envelopes and applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Construction of 1-d lower envelopes and applications

Full text

Pdf (1.50 MB)

Source

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

Nice, France

Pages: 57 - 66

Year of Publication: 1997

ISBN:0-89791-878-9

Author

Edgar A. Ramos

Max-Planck-Institut für Informatik, Im Stadtwald, 66123 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): 4, Downloads (12 Months): 16, Citation Count: 8

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/262839.262864 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	P. K. Agarwal. Geometric partitioning and its applications. In J. E. Goodman, R. Pollack, and W. Steiger, editors, Computational Geometry: Papers from the DIMACS special year. Amer. Math. Soc., 1991.
	2	P.K. Agarwal and J. Matou#ek. On range searching with semialgebraic sets. Discrete Comput. Geom. 11 (1994), 393- 418.
	3	N.M. Amato, M.T. Goodrich, and E.A. Ramos. Parallel algorithms for higher-dimensional convex hulls. In Proc. $Sth Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 9#), 683- 694, 1994.
	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 [doi>10.1145/225058.225285]
	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	M.J. Atallah. Some dynamic computational geometry problems. In Comps. and Moths. with Appls. 11 (1985) 1171- 1181.
	7	Timothy M. Chan, Output-sensitive results on convex hulls, extreme points, and related problems, Proceedings of the eleventh annual symposium on Computational geometry, p.10-19, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220281]
	8	Timothy M. Y. Chan , Jack Snoeyink , Chee-Keng Yap, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.282-291, January 22-24, 1995, San Francisco, California, United States
	9	Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
	10	B. Chazelle, H. Edelsbrunner, L. Guibas and M. Sharir, Diameter, width, closest line pair, and parametric searching, Discrete Comput. Geom. 10 (1993), 183-196.
	11	B. Chazelle and J. Matou#,ek. Derandomizing an output sensitive convex hull algorithm in three dimensions. Technical Report, Dept. of Computer Science, Princeton University, 1992.
	12	Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
	13	K.-W. Chong and E.A. Ramos. Manuscript in preparation. 1997
	14	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]
	15	Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
	16	Richard Cole , Michael T. Goodrich , Colm Ó Dúnlaing, Merging free trees in parallel for efficient Voronoi diagram construction, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.432-445, July 1990, Warwick University, England
	17	D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection. Theoret. Comput. Sci. 27 (1983) 241- 253.
	18	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	19	Herbert Edelsbrunner , Weiping Shi, An O(n log2h) time algorithm for the three-dimensional convex hull problem, SIAM Journal on Computing, v.20 n.2, p.259-269, April 1990 [doi>10.1137/0220016]
	20	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]
	21	Mujtaba R. Ghouse , Michael T. Goodrich, In-place techniques for parallel convex hull algorithms (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.192-203, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113397]
	22	Optimal deterministic approximate parallel prefix sums and their applications, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.220, January 04-06, 1995
	23	Michael T. Goodrich, Using approximation algorithms to design parallel algorithms that may ignore processor allocation (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.711-722, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185439]
	24	Michael T. Goodrich, Geometric partitioning made easier, even in parallel, Proceedings of the ninth annual symposium on Computational geometry, p.73-82, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161002]
	25	Michael T. Goodrich, Fixed-dimensional parallel linear programming via relative &egr;-approximations, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.132-141, January 28-30, 1996, Atlanta, Georgia, United States
	26	M.T. Goodrich, C. 6'Ddnlaing and C.-K. Yap. Constructing the Voronoi diagram of a set of line segments in parallel. Algorithmica 9 (1993) 128-141.
	27	M.T. Goodrich and E.A. Ramos. Bounded independence derandomization of geometric partitioning with applications to parallel fixed-dimensional linear programming. To appear in Discrete and Computational Geometry.
	28	Neelima Gupta , Sandeep Sen, Faster output-sensitive parallel convex hulls for d≤3: optimal sublogarithmic algorithms for small outputs, Proceedings of the twelfth annual symposium on Computational geometry, p.176-185, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237351]
	29	T. Hagerup and R. Raman. Waste makes haste: tight bounds for loose parallel sorting. In Proc. 33th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 92), 628-637, 1992.
	30	A. Heppes, Beweis einer Vermutung yon A. V#izsonyi, Acta Math. Acad. Sci. Hungar. 7 (1956), 463-466.
	31	David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
	32	R. Klein. Concrete and Abstract Voronoi diagrams. LCNS 400, Springer-Verlag, 1988.
	33	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
	34	Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991 [doi>10.1007/BF02574697]
	35	Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
	36	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]
	37	Philip D. MacKenzie , Quentin F. Stout, Ultra-fast expected time parallel algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.414-423, January 28-30, 1991, San Francisco, California, United States
	38	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]
	39	K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1993.
	40	Marco Pellegrini, On point location and motion planning among simplices, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.95-104, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195112]
	41	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	42	Sanguthevar Rajasekaran , Suneeta Ramaswami, Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane and related problems, Proceedings of the tenth annual symposium on Computational geometry, p.57-66, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177511]
	43	Edgar A. Ramos, An algorithm for intersecting equal radius balls in R\u3\d, University of Illinois at Urbana-Champaign, Champaign, IL, 1994
	44	John H. Reif , Sandeep Sen, Optimal parallel randomized algorithms for three-dimensional convex hulls and related problems, SIAM Journal on Computing, v.21 n.3, p.466-485, June 1992 [doi>10.1137/0221031]
	45	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996

CITED BY 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
	Wei Chen , Koichi Wada, On Computing the Upper Envelope of Segments in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.5-13, January 2002
	Timothy M. Chan, Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus, Proceedings of the sixteenth annual symposium on Computational geometry, p.300-309, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	Timothy M. Chan, Geometric applications of a randomized optimization technique, Proceedings of the fourteenth annual symposium on Computational geometry, p.269-278, June 07-10, 1998, Minneapolis, Minnesota, United States
	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
	Edgar A. Ramos, Deterministic algorithms for 3-D diameter and some 2-D lower envelopes, Proceedings of the sixteenth annual symposium on Computational geometry, p.290-299, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	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