Topologically sweeping an arrangement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Topologically sweeping an arrangement

Full text

Pdf (1.29 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 389 - 403

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

H Edelsbrunner	University of Illinois
L J Guibas	DEC/SRC and Stanford University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 82, Citation Count: 25

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/12130.12171 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.

	AA	Asano, T., Asano, T., Guibas, L.J., Hershberger, J., and Imai, H., Vislbility-polygon search and euclidean shortest paths. Proc. 26th Annual FOCS Symposium (1985), 155- 164.
	AHU	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	AR	David Avis , David Rappaport, Computing the largest empty convex subset of a set of points, Proceedings of the first annual symposium on Computational geometry, p.161-167, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323255]
	CGL	Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
	CK	Chvathl, V., and Klincsek, G., Finding largest convex subsets. In Proc. l l t h SE Conf. on Combin., Graph Theory and Comp., 1980.
	E	Edelsbrunner, H., Constructing edge-skeletons in three dimensions dffth applications to power diagrams and dissecting three-dimensional point sets. Report F140, Inst. Inf. Process., Techn. Univ. Graz, 1984. To appear in A1- gorithmica. JEll Edelsbrunner, H., Arrangements and Geometric Computation. To be published.
	EGS	Edelsbrunner, H., Guibas, L.J., and Stolfi, J., Optimal point location in a monotone subdivision. DEC/SRC res. report 2, 1984. To appear in SIAM J. on Comp.
	EOS	H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
	EOW	Edelsbrunner, H., Overmars, M.H., and Wood, D., Graphics in flatland: a case study. In Advances in Computing Research 1, F.P. Preparata, Ed., 1983, 35-59.
	ES1	Erdi~s, P., and Szekeres, G., A combinatorial problem in geometry. Composition Math. 2, 1935, 463-470.
	ES2	ErdSs, P., and Szekeres, G., On some extremum problems in elementary geometry. Ann. Univ. Sci. Budapest 3, 1960, 53-62.
	EW	Edelsbrunner, H., and Welzl, E., Constructing belts in two-dimensional arrangements with applications. SIAM J. Comp., to appear.
	Pr	Fredman, M.L., On the information theoretic lower bound. Theor. Comp. Sc. 1 (1976), 355-361.
	FT	Fredman, M.L., and Tarjan, R.E., Fibonacci heaps and their uses in improved network optimization algorithms. Proc. 21st Ann. FOGS SYmposium, 1984, 338-346.
	G	Grfinbaum, B., Arrangements and Spreads. Reg. Conf. Ser. Math., AMS, 1972.
	Gu	Guibas, L.J., On a space-time trade-off for a backtracking problem. In preparation.
	GS	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	Ha	Harborth, H., Konvexe Fanfecke in ebenen Punkmengen. Elem. Math. 33, 1978, 116-118.
	Ho	Horton, J.D., Sets with no empty convex 7-yon. Canad. Math. Bull. 26, 1983, 482-484.
	Kn	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	L	Der-Tsai Lee, Proximity and reachability in the plane., 1978
	LP	Lee, D.T., and Preparata, F.P., Euclidean shortest paths in the presence of rectilinear barriers. Network 14, 1984, 393-410.
	MS	Michael McKenna , Raimund Seidel, Finding the optimal shadows of a convex polytope, Proceedings of the first annual symposium on Computational geometry, p.24-28, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323237]
	NP	J. Nievergelt , F. P. Preparata, Plane-sweep algorithms for intersecting geometric figures, Communications of the ACM, v.25 n.10, p.739-747, Oct 1982 [doi>10.1145/358656.358681]
	Ps	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	Sh	Sharir, M., personal communication, 1985.
	T	Tarjan, R.E., Amortized computational complexity. J. on Comp., to appear.
	W	Welzl, W., Constructing the visibility graph segments in O(n 2) time. Inf. Proc. Letters 20, 171.

CITED BY 25

	Steven Fortune , Victor Milenkovic, Numerical stability of algorithms for line arrangements, Proceedings of the seventh annual symposium on Computational geometry, p.334-341, June 10-12, 1991, North Conway, New Hampshire, United States
	M. McKenna , J. O'Rourke, Arrangements of lines in 3-space: a data structure with applications, Proceedings of the fourth annual symposium on Computational geometry, p.371-380, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	D. P. Dobkin , H. Edelsbrunner , M. H. Overmars, Searching for empty convex polygons, Proceedings of the fourth annual symposium on Computational geometry, p.224-228, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992
	Nora H. Sleumer, Output-sensitive cell enumeration in hyperplane arrangements, Nordic Journal of Computing, v.6 n.2, p.137-147, Summer 1999
	Michael T. Goodrich, Constructing arrangements optimally in parallel (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.169-179, July 21-24, 1991, Hilton Head, South Carolina, United States
	B. Chazelle , H. Edelsbrunner , L. Guibas, The complexity of cutting convex polytypes, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.66-76, January 1987, New York, New York, United States
	L. J. Guibas , M. Sharir , S. Sifrony, On the general motion planning problem with two degrees of freedom, Proceedings of the fourth annual symposium on Computational geometry, p.289-298, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	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
	L Guibas , R Seidel, Computing convolutions by reciprocal search, Proceedings of the second annual symposium on Computational geometry, p.90-99, June 02-04, 1986, Yorktown Heights, New York, United States
	Torben Hagerup , H. Jung , E. Welzl, Efficient parallel computation of arrangements of hyperplanes in d dimensions, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.290-297, July 02-06, 1990, Island of Crete, Greece
	M. H. Overmars , E. Welzl, New methods for computing visibility graphs, Proceedings of the fourth annual symposium on Computational geometry, p.164-171, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	J. Snoeyink , J. Hershberger, Sweeping arrangements of curves, Proceedings of the fifth annual symposium on Computational geometry, p.354-363, June 05-07, 1989, Saarbruchen, West Germany
	Stéphane Rivière, Topologically sweeping the visibility complex of polygonal scenes, Proceedings of the eleventh annual symposium on Computational geometry, p.436-437, June 05-07, 1995, Vancouver, British Columbia, Canada
	Michael McKenna, Worst-case optimal hidden-surface removal, ACM Transactions on Graphics (TOG), v.6 n.1, p.19-28, Jan. 1987
	Binay Bhattacharya , Jurek Czyzowicz , Peter Egyed , Ivan Stojmenovic , Godfried Toussaint , Jorge Urrutia, Computing shortest transversals of sets (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.71-80, June 10-12, 1991, North Conway, New Hampshire, United States
	Marc H. Brown , John Hershberger, Color and Sound in Algorithm Animation, Computer, v.25 n.12, p.52-63, December 1992
	Ioannis Emiris , John Canny, An efficient approach to removing geometric degeneracies, Proceedings of the eighth annual symposium on Computational geometry, p.74-82, June 10-12, 1992, Berlin, Germany
	David Eppstein, New algorithms for minimum area k-gons, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.83-88, September 1992, Orlando, Florida, United States
	Christian Ronse, A Bibliography on Digital and Computational Convexity (1961-1988), IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.181-190, February 1989
	H. Edelsbrunner , E. P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, Proceedings of the fourth annual symposium on Computational geometry, p.118-133, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Michael T. Goodrich, Applying parallel processing techniques to classification problems in constructive solid geometry, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.118-128, January 22-24, 1990, San Francisco, California, United States
	M. T. Goodrich, Intersecting line segments in parallel with an output-sensitive number of processors, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.127-137, June 18-21, 1989, Santa Fe, New Mexico, United States
	Johannes Zimmermann , Andrew Nealen , Marc Alexa, SilSketch: automated sketch-based editing of surface meshes, Proceedings of the 4th Eurographics workshop on Sketch-based interfaces and modeling, August 02-03, 2007, Riverside, California
	Johannes Zimmermann , Andrew Nealen , Marc Alexa, Sketch-based Interfaces: Sketching contours, Computers and Graphics, v.32 n.5, p.486-499, October, 2008