MAPC

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

MAPC: a library for efficient and exact manipulation of algebraic points and curves

Full text

Pdf (1.20 MB)

Source

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

Miami Beach, Florida, United States

Pages: 360 - 369

Year of Publication: 1999

ISBN:1-58113-068-6

Authors

John Keyser	Department of Computer Science, University of North Carolina, Chapel Hill, NC
Tim Culver	Department of Computer Science, University of North Carolina, Chapel Hill, NC
Dinesh Manocha	Department of Computer Science, University of North Carolina, Chapel Hill, NC
Shankar Krishnan	AT & T Research Labs and Department of Computer Science, University of North Carolina, Chapel Hill, NC

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): 13, Citation Count: 17

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

	ABB+92	E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
	ABD+94	F. Avnaim, J.-D. Boissonnat, O. Devillers, F. Preparata, and M. Yvinec. Evaluating signs of determinants using single-precision arithmetic. Research Report 2306, INRIA, BP93, 06902 Sophia-Antipolis, France, 1994.
	ACM84a	Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984 [doi>10.1137/0213054]
	ACM84b	Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition II: an adjacency algorithm for the plane, SIAM Journal on Computing, v.13 n.4, p.878-889, Nov. 1984 [doi>10.1137/0213055]
	AF88	Stefan Arnborg , Huichun Feng, Algebraic decomposition of regular curves, Journal of Symbolic Computation, v.5 n.1-2, p.131-140, February/April 1988 [doi>10.1016/S0747-7171(88)80009-9]
	BBP95	I. Biehl, J. Buchmann, and T. Papanikolaou. Lidia: A library for computational number theory. Technical Report SFB 124-C1, Fachbereich Informatik, Universitt des Saarlandes, 1995.
	BEPP97	Hervé Brönnimann , Ioannis Z. Emiris , Victor Y. Pan , Sylvain Pion, Computing exact geometric predicates using modular arithmetic with single precision, Proceedings of the thirteenth annual symposium on Computational geometry, p.174-182, June 04-06, 1997, Nice, France [doi>10.1145/262839.262948]
	Can87	John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
	CKM98	Tim Culver , John Keyser , Dinesh Manocha, Accurate computation of the medial axis of a polyhedron, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.179-190, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304030]
	Dav93	J. H. Davenport , Y. Siret , E. Tournier, Computer algebra (2nd ed.): systems and algorithms for algebraic computation, Academic Press Professional, Inc., San Diego, CA, 1993
	Dem98	J. Demmel. Private Communication, 1998.
	DK90	James Demmel , W. Kahan, Accurate singular values of bidiagonal matrices, SIAM Journal on Scientific and Statistical Computing, v.11 n.5, p.873-912, September 1990 [doi>10.1137/0911052]
	FGK+96	Andreas Fabri , Geert-Jan Giezeman , Lutz Kettner , Stefan Schirra , Sven Schönherr, The CGAL Kernel: A Basis for Geometric Computation, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.191-202, May 27-28, 1996
	For95	Steven Fortune. Voronoi diagrams and delaunay triangulations. In D. Z. Du and F. Hwang, editors, Computing in Euclidean Geometry, pages 225-265. World Scientific Press, Singapore, 1995.
	FV93	Steven Fortune , Christopher J. Van Wyk, Efficient exact arithmetic for computational geometry, Proceedings of the ninth annual symposium on Computational geometry, p.163-172, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161015]
	Hof89	Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
	KCMK98	John Keyser , Tim Culver , Dinesh Manocha , Shankar Krishnan, MAPC: A library for Efficient and Exact Manipulation of Algebraic Points and Curves, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1998
	KKM97	John Keyser , Shankar Krishnan , Dinesh Manocha, Efficient and accurate B-rep generation of low degree sculptured solids using exact arithmetic, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.42-55, May 14-16, 1997, Atlanta, Georgia, United States [doi>10.1145/267734.267753]
	KKMC98	John Keyser , Shankar Krishnan , Dinesh Manocha , Tim Culver, Efficient and Reliable Computation with Algebraic Numbers for Geometric Algorithms, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1998
	KLN91	Michael Karasick , Derek Lieber , Lee R. Nackman, Efficient Delaunay triangulation using rational arithmetic, ACM Transactions on Graphics (TOG), v.10 n.1, p.71-91, Jan. 1991 [doi>10.1145/99902.99905]
	Knu69	Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	KYP92	David J. Kriegman, Erliang Yeh, and Jean Ponce. Convex hulls of algebraic curves. In J. D. Warren, editor, Proceedings o} the Inter. national Society for Optical Engineering Volume 1830, Curves and Sur}aces in Computer Vision and Graphics IIl, pages 118-127. SPIE, Boston, 1992.
	MC93	Dinesh Manocha , John F. Canny, Multipolynomial resultant algorithms, Journal of Symbolic Computation, v.15 n.2, p.99-122, Feb. 1993 [doi>10.1006/jsco.1993.1009]
	Mil92	P.S. Milne. On the solutions of a set of polynomial equations. In Symbolic and Numerical Computation for Artificial Intelligence, pages 89-102, 1992.
	MN89	K. Mehlhorn and S. Naher. LEDA, a library of efficient data types and algorithms. Report A 04/89, Fachber. Inform., Univ. Saarlandes, Saarbr/icken, West Germany, 1989.
	Ped91	Paul Pedersen, Multivariate Sturm Theory, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.318-332, October 07-11, 1991
	Reg96	Ashutosh Gajanan Rege , John Canny, A toolkit for algebra and geometry, 1996
	She97	Jonathan Richard Shewchuk. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete # Computational Geometry, 18(3):305-363, October 1997.
	SP95	Evan C. Sherbrooke , Nicholas M. Patrikalakis , Erik Brisson, Computation of the Medial Axis Transform of 3-D polyhedra, Proceedings of the third ACM symposium on Solid modeling and applications, p.187-200, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218059]
	Yu92	Jiaxun Yu, Exact arithmetic solid modeling, Purdue University, West Lafayette, IN, 1992

CITED BY 17

	Nicola Geismann , Michael Hemmer , Elmar Schömer, Computing a 3-dimensional cell in an arrangement of quadrics: exactly and actually!, Proceedings of the seventeenth annual symposium on Computational geometry, p.264-273, June 2001, Medford, Massachusetts, United States
	Tim Culver , John Keyser , Dinesh Manocha, Accurate computation of the medial axis of a polyhedron, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.179-190, June 08-11, 1999, Ann Arbor, Michigan, United States
	Nicola Geismann , Michael Hemmer , Elmar Schömer, The convex hull of ellipsoids, Proceedings of the seventeenth annual symposium on Computational geometry, p.321-322, June 2001, Medford, Massachusetts, United States
	Menelaos I. Karavelas , Ioannis Z. Emiris, Root comparison techniques applied to computing the additively weighted Voronoi diagram, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Arno Eigenwillig , Lutz Kettner , Elmar Schömer , Nicola Wolpert, Complete, exact, and efficient computations with cubic curves, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Erich Kaltofen , Gilles Villard, Computing the sign or the value of the determinant of an integer matrix, a complexity survey, Journal of Computational and Applied Mathematics, v.162 n.1, p.133-146, 1 January 2004
	Tim Culver , John Keyser , Dinesh Manocha, Exact computation of the medial axis of a polyhedron, Computer Aided Geometric Design, v.21 n.1, p.65-98, January 2004
	Steven Fortune, Exact computations of the inertia symmetric integer matrices, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.556-564, May 21-23, 2000, Portland, Oregon, United States
	Shankar Krishnan , Mark Foskey , Tim Culver , John Keyser , Dinesh Manocha, PRECISE: efficient multiprecision evaluation of algebraic roots and predicates for reliable geometric computation, Proceedings of the seventeenth annual symposium on Computational geometry, p.274-283, June 2001, Medford, Massachusetts, United States
	Eyal Flato , Dan Halperin , Iddo Hanniel , Oren Nechushtan , Eti Ezra, The design and implementation of panar maps in CGAL, Journal of Experimental Algorithmics (JEA), 5, p.13-es, 2000
	Eric Berberich , Michael Hemmer , Lutz Kettner , Elmar Schömer , Nicola Wolpert, An exact, complete and efficient implementation for computing planar maps of quadric intersection curves, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Elmar Schömer , Nicola Wolpert, An exact and efficient approach for computing a cell in an arrangement of quadrics, Computational Geometry: Theory and Applications, v.33 n.1-2, p.65-97, January 2006
	Arno Eigenwillig , Lutz Kettner , Elmar Schömer , Nicola Wolpert, Exact, efficient, and complete arrangement computation for cubic curves, Computational Geometry: Theory and Applications, v.35 n.1, p.36-73, August 2006
	Hoon Hong , Erich Kaltofen , Michael Singer, East Coast Computer Algebra Day '99 (April 24, 1999): abstracts of invited talks and presented posters, ACM SIGSAM Bulletin, v.33 n.2, p.43-52, June 1999
	Pedro M. M. de Castro , Frédéric Cazals , Sébastien Loriot , Monique Teillaud, Design of the CGAL 3D Spherical Kernel and application to arrangements of circles on a sphere, Computational Geometry: Theory and Applications, v.42 n.6-7, p.536-550, August, 2009
	Abel J. P. Gomes , José F. M. Morgado , Edgar S. Pereira, A BSP-based algorithm for dimensionally nonhomogeneous planar implicit curves with topological guarantees, ACM Transactions on Graphics (TOG), v.28 n.2, p.1-24, April 2009
	Andre Schollmeyer , Bernd Fröhlich, Direct trimming of NURBS surfaces on the GPU, ACM Transactions on Graphics (TOG), v.28 n.3, August 2009