Computing exact geometric predicates using modular arithmetic with single precision

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing exact geometric predicates using modular arithmetic with single precision

Full text

Pdf (1.28 MB)

Source

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

Nice, France

Pages: 174 - 182

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Hervé Brönnimann	INRIA Sophia-Antipolis, B.P. 93, 2004, Route des Lucioles, 06902 Sophia-Antipolis Cedex, France
Ioannis Z. Emiris	INRIA Sophia-Antipolis, B.P. 93, 2004, Route des Lucioles, 06902 Sophia-Antipolis Cedex, France
Victor Y. Pan	Department of Mathematics and Computer Science, Lehman College, City University of New-York, Bronx NY
Sylvain Pion	INRIA Sophia-Antipolis, B.P. 93, 2004, Route des Lucioles, 06902 Sophia-Antipolis Cedex, France

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): 10, Downloads (12 Months): 27, Citation Count: 16

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.262948 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	F. Avnaim , J.-D. Boissonnat , O. Devillers , F. P. Preparata , M. Yvinec, Evaluation of a new method to compute signs of determinants, Proceedings of the eleventh annual symposium on Computational geometry, p.416-417, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220329]
	3	Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
	4	Hervé Brönnimann , Mariette Yvinec, Efficient exact evaluation of signs of determinants, Proceedings of the thirteenth annual symposium on Computational geometry, p.166-173, June 04-06, 1997, Nice, France [doi>10.1145/262839.262944]
	5	B. Buchberger , George E. Collins , Rudiger Loos , Rudolf Albrecht, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
	6	C. Burnikel , J. Könemann , K. Mehlhorn , S. Näher , S. Schirra , C. Uhrig, Exact geometric computation in LEDA, Proceedings of the eleventh annual symposium on Computational geometry, p.418-419, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220330]
	7	K. L. Clarkson. Safe and effective determinant evaluation. In Proc. 33rd Annu. IEEE Sympos. Found. Comput. Sci., pages 387-395, 1992.
	8	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	9	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]
	10	I.Z. Emiris. A complete implementation for computing general dimensional convex hulls. Intern. J. Computational Geom. # Applications, 1997. To appear. Preliminary version as Tech. Report 2551, INRIA Sophia-Antipolis, France, 1995.
	11	Ioannis Z. Emiris , John F. Canny, A General Approach to Removing Degeneracies, SIAM Journal on Computing, v.24 n.3, p.650-664, June 1995 [doi>10.1137/S0097539792235918]
	12	Steven Fortune, Numerical stability of algorithms for 2D Delaunay triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.83-92, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142695]
	13	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]
	14	Steven Fortune , Christopher J. Van Wyk, Static analysis yields efficient exact integer arithmetic for computational geometry, ACM Transactions on Graphics (TOG), v.15 n.3, p.223-248, July 1996 [doi>10.1145/231731.231735]
	15	I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky. Discriminants and Resultants. Birkh#user, Boston, 1994.
	16	G. H. Golub and C. F. van Loan Matrix computations. Johns Hopkins University Press, Baltimore, Maryland, 1996.
	17	C. M. Hoffmann. The problem of accuracy and robustness in geometric computation. Report CSD- TR-771, Dept. Comput. Sci., Purdue Univ., West Lafayette, IN, 1988.
	18	Christoph M. Hoffmann, How Solid is Solid Modeling?, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.1-8, May 27-28, 1996
	19	Christoph M. Hoffmann , John E. Hopcroft , Michael E. Karasick, Robust Set Operations on Polyhedral Solids, IEEE Computer Graphics and Applications, v.9 n.6, p.50-59, November 1989 [doi>10.1109/38.41469]
	20	C.Y. Hung, B. Parhami. An approximate sign detection method for residue numbers and its application to RNS division. Computers Math. Applic. 27(4):23-35, 1994.
	21	John Keyser , Shankar Krishnan , Dinesh Manocha, Efficient B-rep Generation of Low-Degree Sculptured Solids Using Exact Arithmetic, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1996
	22	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	23	M. Lauer. Computing by homomorphic images. In B. Buchberger, G.E. Collins, and R. Loos, editors, Computer Algebra: Symbolic and Algebraic Computation, pages 139-168. Springer, Wien, 2nd edition, 1982.
	24	M.C. Lin, D. Manocha, and J. Canny. Efficient contact determination for dynamic environments. In Proc. IEEE Conf. Robotics and Automation, pages 602-608, 1994.
	25	V. Y. Pan, Y. Yu, and C. Stewart. Algebraic and numerical techniques for the computation of matrix determinants. Computers # Math. (with Applications), 1997, to appear.
	26	Victor Y. Pan, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Theoretical Computer Science, v.162 n.2, p.173-223, Aug. 20, 1996 [doi>10.1016/0304-3975(96)00030-8]
	27	Ashutosh Rege, A complete and practical algorithm for geometric theorem proving (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.277-286, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220309]
	28	Johnathan Richard Shewchuk, Robust adaptive floating-point geometric predicates, Proceedings of the twelfth annual symposium on Computational geometry, p.141-150, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237337]
	29	K. Sugihara and M. Iri. A robust topology-oriented incremental algorithm for Voronoi diagrams. Internat. J. Comput. Geom. Appl., 4:179-228, 1994.
	30	J. Wiegley, A. Rao, and K. Goldberg. Computing a statistical distribution of stable poses for a polyhedron, in Proc. 30th Annual Allerton Conf. on Comm. Control and Computing, Univ.Ill. Urbana- Champaign, 1992.
	31	Chee-Keng Yap, Towards exact geometric computation, Computational Geometry: Theory and Applications, v.7 n.1-2, p.3-23, Jan. 1997 [doi>10.1016/0925-7721(95)00040-2]
	32	C. K. Yap. Exact computational geometry and tolerancing metrology. In D. Avis and J. Bose, editors, Snapshots of Computational and Discrete Geometry, Vol. 3, Tech. Rep. SOCS-94.50. McGill School of Comp. Sci., 1995.
	33	C. K. Yap and T. Dubhe. The exact computation paradigm. In D. Du and F. Hwang, editors, Computing in Euclidean Geometry. World Scientific Press, 1995.

CITED BY 16

	Steven Fortune, Vertex-rounding a three-dimensional polyhedral subdivision, Proceedings of the fourteenth annual symposium on Computational geometry, p.116-125, June 07-10, 1998, Minneapolis, Minnesota, United States
	Victor Y. Pan , Yanqiang Yu, Certified computation of the sign of a matrix determinant, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.715-724, January 17-19, 1999, Baltimore, Maryland, United States
	V. Karamcheti , C. Li , I. Pechtchanski , C. Yap, A core library for robust numeric and geometric computation, Proceedings of the fifteenth annual symposium on Computational geometry, p.351-359, June 13-16, 1999, Miami Beach, Florida, 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
	Bernd Gärtner, Exact arithmetic at low cost—a case study in linear programming, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.157-166, January 25-27, 1998, San Francisco, California, 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
	Abbas Edalat , André Lieutier, Foundation of a computable solid modeling, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.278-284, June 08-11, 1999, Ann Arbor, Michigan, United States
	Jean-Daniel Boissonnat , Jack Snoeyink, Efficient algorithms for line and curve segment intersection using restricted predicates, Proceedings of the fifteenth annual symposium on Computational geometry, p.370-379, June 13-16, 1999, Miami Beach, Florida, United States
	Hervé Brönnimann , Christoph Burnikel , Sylvain Pion, Interval arithmetic yields efficient dynamic filters for computational geometry, Proceedings of the fourteenth annual symposium on Computational geometry, p.165-174, June 07-10, 1998, Minneapolis, Minnesota, United States
	Sigal Raab, Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes, Proceedings of the fifteenth annual symposium on Computational geometry, p.163-172, June 13-16, 1999, Miami Beach, Florida, United States
	John Abbott , Manuel Bronstein , Thom Mulders, Fast deterministic computation of determinants of dense matrices, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.197-204, July 28-31, 1999, Vancouver, British Columbia, Canada
	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
	John Keyser , Tim Culver , Dinesh Manocha , Shankar Krishnan, MAPC: a library for efficient and exact manipulation of algebraic points and curves, Proceedings of the fifteenth annual symposium on Computational geometry, p.360-369, June 13-16, 1999, Miami Beach, Florida, United States
	John Keyser , Tim Culver , Mark Foskey , Shankar Krishnan , Dinesh Manocha, ESOLID---A System for Exact Boundary Evaluation, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Jean-Claude Bajard , Laurent-Stéphane Didier , Jean-Michel Muller, A New Euclidean Division Algorithm for Residue Number Systems, Journal of VLSI Signal Processing Systems, v.19 n.2, p.167-178, July 1998
	Alexey Lvov , Ulrich Finkler, Exact basic geometric operations on arbitrary angle polygons using only fixed size integer coordinates, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California