On the complexity of the union of fat objects in the plane

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of the union of fat objects in the plane

Full text

Pdf (1.01 MB)

Source

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

Nice, France

Pages: 104 - 112

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Alon Efrat	School of Mathematical Sciences, Tel Aviv University
Micha Sharir	School of Mathematical Sciences, Tel Aviv University and Courant Institute of Mathematical Sciences, New York University

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): 1, Downloads (12 Months): 15, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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.262911 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 , Matthew J. Katz , Micha Sharir, Computing depth orders for fat objects and related problems, Computational Geometry: Theory and Applications, v.5 n.4, p.187-206, Nov. 1995 [doi>10.1016/0925-7721(95)00005-8]
	2	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]
	3	Alon Efrat , Micha Sharir , Alon Ziv, Computing the smallest k-enclosing circle and related problems, Computational Geometry: Theory and Applications, v.4 n.3, p.119-136, July 1994 [doi>10.1016/0925-7721(94)90003-5]
	4	D. Halperin and M. Sharir, Almost tight upper bounds for the single cell and zone problems in three dimensions, Diacrete Comput. Geom. 14 (1995), 385-410.
	5	Matthew J. Kaltz, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, Computational Geometry: Theory and Applications, v.8 n.6, p.299-316, Nov. 1997 [doi>10.1016/S0925-7721(96)00027-2]
	6	Matthew J. Katz , Mark H. Overmars , Micha Sharir, Efficient hidden surface removal for objects with small union size, Computational Geometry: Theory and Applications, v.2 n.4, p.223-234, Dec. 1992 [doi>10.1016/0925-7721(92)90024-M]
	7	Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
	8	László Lovász, On Conway's thrackle conjecture, Proceedings of the eleventh annual symposium on Computational geometry, p.147-151, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220295]
	9	Jiri Matousek , Janos Pach , Micha Sharir , Shmuel Sifrony , Emo Welzl, Fat Triangles Determine Linearly Many Holes, SIAM Journal on Computing, v.23 n.1, p.154-169, Feb. 1994 [doi>10.1137/S009753979018330X]
	10	J. Pach and M. Sharir, On the boundary of the union of planar convex sets, manuscript, 1997.
	11	M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete Comput. Geom. 6 (1991), 593-613.
	12	M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions, Discrete Cornput. Geom. 12 (1994), 327-345.
	13	F. van der S#appen, Motion Planning amidst Fat Obatacles, Ph.D. Dissertation, Utrecht University, 1994.
	14	Marc J. van Kreveld, On Fat Partitioning, Fat Covering and the Union Size of Polygons (Extended Abstract), Proceedings of the Third Workshop on Algorithms and Data Structures, p.452-463, August 11-13, 1993

CITED BY 9

	Mirela Damian, Exact and approximation algorithms for computing optimal fat decompositions, Computational Geometry: Theory and Applications, v.28 n.1, p.19-27, May 2004
	Yunhong Zhou , Subhash Suri, Analysis of a bounding box heuristic for object intersection, Journal of the ACM (JACM), v.46 n.6, p.833-857, Nov. 1999
	Yunhong Zhou , Subhash Suri, Analysis of a bounding box heuristic for object intersection, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.830-839, January 17-19, 1999, Baltimore, Maryland, United States
	Alon Efrat, The complexity of the union of (&agr;, &bgr;)-covered objects, Proceedings of the fifteenth annual symposium on Computational geometry, p.134-142, June 13-16, 1999, Miami Beach, Florida, United States
	Alon Efrat , Matthew J. Katz, On the union of κ-curved objects, Proceedings of the fourteenth annual symposium on Computational geometry, p.206-213, June 07-10, 1998, Minneapolis, Minnesota, United States
	Subhash Suri , Philip M. Hubbard , John F. Hughes, Analyzing bounding boxes for object intersection, ACM Transactions on Graphics (TOG), v.18 n.3, p.257-277, July 1999
	Mark de Berg, Vertical ray shooting for fat objects, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Pankaj K. Agarwal , Micha Sharir, Motion planning of a ball amid segments in three dimensions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.21-30, January 17-19, 1999, Baltimore, Maryland, United States
	Christian A. Duncan , Michael T. Goodrich , Stephen Kobourov, Balanced aspect ratio trees: combining the advantages of k-d trees and octrees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.300-309, January 17-19, 1999, Baltimore, Maryland, United States