Raising roofs, crashing cycles, and playing pool

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 and J. Erickson. Geometric ranso searching and its relatives. Technical report CS-1997-11, Duke University, May 1997. To appear in Discrete # C'omputatzonal Geome#y: Ten Years Later, B. Chazelle, J. E. Goodman, and R. Pollack, editors, American Mathematical Society Prcsa, 1998. (http://www.cs.duke.edu/"jeffe/pub#/survey.ht ml).
	2	P. K. Agarwal and J. Matou#ek. Dynamic half-space range reporting and its applications. Algorithmica 13:325-345, 1995.
	3	Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, SIAM Journal on Computing, v.22 n.4, p.794-806, Aug. 1993 [doi>10.1137/0222051]
	4	P. K. Agarwal and J. Matou#ek. On range searching with semialgebraic sets. Discrete Comput. Geom. 11:393-418, 1994.
	5	Pankaj K. Agarwal , Micha Sharir, Applications of a new space-partitioning technique, Discrete & Computational Geometry, v.9 n.1, p.11-38, 1993 [doi>10.1007/BF02189304]
	6	A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
	7	Oswin Aichholzer , Franz Aurenhammer, Straight Skeletons for General Polygonal Figures in the Plane, Proceedings of the Second Annual International Conference on Computing and Combinatorics, p.117-126, June 17-19, 1996
	8	O. Aichhoher, F. Aurenhammer, D. Alberts, and B. G#tncr. A novel type of skeleton for polygons. J. Universal Comput. Sci. 1(12):752-761, 1995. (http://vnvw.iicm.edu}juco#l.12/ amoveLt3rpe_of).
	9	M, J0 Atallah, P, Callahan# and M. T. Goodrich. P-complete geometric problems. Internal J. Comput. Geom. AppL 3:443-462, 1993,
	10	David Baraff, Interactive Simulation of Solid Rigid Bodies, IEEE Computer Graphics and Applications, v.15 n.3, p.63-75, May 1995 [doi>10.1109/38.376615]
	11	Julien Basch , Leonidas J. Guibas , John Hershberger, Data structures for mobile data, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.747-756, January 05-07, 1997, New Orleans, Louisiana, United States
	12	Julien Basch , Leonidas J. Guibas , Li Zhang, Proximity problems on moving points, Proceedings of the thirteenth annual symposium on Computational geometry, p.344-351, June 04-06, 1997, Nice, France [doi>10.1145/262839.262998]
	13	M, de Berg, D, Halperin, M. Overmars, J. Snoeyink, and M. van Kreveld. Efficient ray shooting and hidden surface removal, Algorithmica 12:30-53, 1994.
	14	H. Blum, A transformation for extracting new descriptors of #hape, Models for the Perception of Speech and Visual Form, pp, 362-380. HIT Press, 1967.
	15	F, L, BookDtein, The line-skeleton. CompuL Graph. Image Proceso. II:123-137, 1979.
	16	L. Calabt and W, E. Hartnett. Shape recognition, prairie flreu, convex deficiencies and skeletons. Amer. Math. Monthly 75:335-342, 1968.
	17	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 [doi>10.1145/276884.276915]
	18	Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, v.84 n.1, p.77-105, July 22, 1991 [doi>10.1016/0304-3975(91)90261-Y]
	19	B, Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, and J, Stolfl, Lines in apace: Combinatorics and algorithms. Algorithmica 15:428-447, 1996,
	20	L, P, Chert. Building Voronoi diagrams for convex polygons In linear e:vpected time. Technical Report PCS-TR90-147, Dept. Math. Comput. Sci., Dartmouth College, 1986.
	21	Francis Y. Chin , Jack Snoeyink , Cao An Wang, Finding the Medial Axis of a Simple Polygon in Linear Time, Proceedings of the 6th International Symposium on Algorithms and Computation, p.382-391, December 04-06, 1995
	22	Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav Ponamgi, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.189-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199437]
	23	Jurek Czyzowicz , Ivan Rival , Jorge Urrutia, Galleries, Light Matchings and Visibility Graphs, Proceedings of the Workshop on Algorithms and Data Structures, p.316-324, August 17-19, 1989
	24	O, Devlllers. Randomization yields simple O{nlog* n) algorlthm# for difficult F2{n) problems. Internal J. CompuL Geom. AppL 2(1):97-111, 1992. (http://www.mria.fr/ prtQme/blblio/search,html).
	25	D, Eppsteln. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete CompuL Geom. 13:111-122, 1995,
	26	David Eppstein, Fast hiearchical clustering and other applications of dynamic closet pairs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.619-628, January 25-27, 1998, San Francisco, California, United States
	27	A. Foloy, V, Hayv/ard, and S. Aubry. The use of awareness in collloton prediction. Prec. 1990 IEEE Internal Conf. Robotics and Automation, pp. 338-343# 1990.
	28	E. Fredkin and T, Toffoli. Conservative logic. In#ernat. J. Theoret, Phy8. 21:219-253, 1981/82. Proceedings of Conference on PhyBics of Computation, Dedham, Mass., 1981.
	29	D, Grlffeath and C. Moore. Life Without Death is P- complete. Working Paper 97-05-044, Santa Fe Institute, 1997, To appear in Complex Systems. (http:// p0oup, math.wiac.edu/java/lwodpc/lwodpc.html).
	30	Leonidas J. Guibas, Kinetic data structures: a state of the art report, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, p.191-209, August 1998, Houston, Texas, United States
	31	H. N. Gfimoy and N. M. Patrikalakis. An automatic coarse and fine surface mesh generation scheme based on medial axis transform, Part h Algorithms. Engineering with Computers 8:121-137, 1992.
	32	M. Held. Voronoi diagrams and offset curves of curvilinear polygons. To appear in CompuL Aided Design. (http:// www.cosy.sbg.ac.at/'held/papers/cad96.p#.#).
	33	M. Held, G. Luk#cs, and L. Andor. Pocket machining based on contour-parallel tool paths generated by means of proximity maps. GompuL Aided Design 26(3):189--203, Mar. 1994.
	34	Philip M. Hubbard, Collision Detection for Interactive Graphics Applications, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.218-230, September 1995 [doi>10.1109/2945.466717]
	35	Dong Jin Kim , Leonidas J. Guibas , Sung Yong Shin, Fast collision detection among multiple moving spheres, Proceedings of the thirteenth annual symposium on Computational geometry, p.373-375, June 04-06, 1997, Nice, France [doi>10.1145/262839.263007]
	36	R. Klein. Goncrefe and Abstract Voronoi Diagrams. Lecture Notes Comput. Sci. 400. Springer-Verlag, 1989.
	37	Robert J. Lang, A computational algorithm for origami design, Proceedings of the twelfth annual symposium on Computational geometry, p.98-105, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237249]
	38	D. T. Lee. Medial axis transformation of a planar shape. IEEE Trans. Pa#ern Anal. Mach. InteU. PAMI-4:363-369, 1982.
	39	S. Lisberger, director. Tron. Walt Disney Productions, 1932. Motion picture, 96 minutes.
	40	Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
	41	J. Matou#ek. Range searching with efficient hierarchical cuttings. D#scre#e CompuL Geom. 10(2):157-182, 1993.
	42	M. McAllister, D. Kirkpatrick, and J. Snoeyink. A compact piecewise-linear Voronoi diagram for convex site# in the plane. Discrete Comput. Geom. 15:73-I05, 1996.
	43	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]
	44	Brian Mirtich , John Canny, Impulse-based simulation of rigid bodies, Proceedings of the 1995 symposium on Interactive 3D graphics, p.181-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199436]
	45	C. 6'Ddnlaing and C. K. Yap. A "retraction" method for planning the motion of a disk. J. Algorithms 6:104--111, 1985.
	46	A. Recuaero and J. P. Gutidrre#. Sloped roofs for archEecrural CAD systems. Microcomputers in Civil Engineering 8:147-159, 1993.
	47	V. Srinivasan, L. R. Nadunan, J.-M. Tang, and S. N. Meshkat. Automatic mesh generation using the symmetric axis transform of polygonal domains. Prec. IEEE 80(9):1485--1501, Sept. 1992.
	48	Jorge Stolfi, Oriented projective geometry, Academic Press Professional, Inc., San Diego, CA, 1991
	49	James A. Storer , John H. Reif, Shortest paths in the plane with polygonal obstacles, Journal of the ACM (JACM), v.41 n.5, p.982-1012, Sept. 1994 [doi>10.1145/185675.185795]
	50	A. Sudhaltmr, L. Gumoz, and F. Prinz. B#-skeletons of discrete solids. CompuL Aided Design 28:507-517, 1996.
	51	T. K. H. Tam and C. G. Armstrong. 2D finite element mesh generation by" medial axis subdivision. Advances in Engi. neering Software and Workstations 13(5-6):313-324# SepL 1991.
	52	P. J. Venneer. MedioJ Axis Transform to Boundary R#re. sensation Conv#rsio# Ph.D. thesis, CS Dept., Purdue University, West Lafayette, Indiana 47907-1398, USA, 1994.