Efficient exact evaluation of signs of determinants

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient exact evaluation of signs of determinants

Full text

Pdf (1.03 MB)

Source

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

Nice, France

Pages: 166 - 173

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Hervé Brönnimann	INRIA Sophia-Antipolis, BP 93, 06902 Sophia-Antipolis, cedex (France)
Mariette Yvinec	INRIA Sophia-Antipolis and CNRS, Laboratoire I3S, BP 145, 06903 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): 3, Downloads (12 Months): 25, Citation Count: 5

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.262944 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.

	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.
	ABD+95	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]
	BKM+95	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]
	C+96	B. Chazelle et al. Application challenges to computational geometry: CG impact task force report. Technical Report TR-521-96, Princeton Univ.. April 1996.
	Cla92	K.L. Clarkson. Safe and effective determinant evaluation. In Proc. 33rd A nnu. IEEE Sympos. Found. Comput. Sci., pages 387- 395, 1992.
	DP96	Olivier Devillers , Franco P. Preparata, A Probabilistic Analysis of the Power of Arithmetic Filters, Brown University, Providence, RI, 1996
	FM67	G. Forsythe and C. Moler. Computer solutions of linear algebraic systems. Prentice Hall, 1967.
	For92	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]
	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]
	HHK88	C. M. Hoffmann , J. E. Hopcroft , M. S. Karasick, Towards implementing robust geometric computations, Proceedings of the fourth annual symposium on Computational geometry, p.106-117, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73405]
	Hof89	Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
	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]
	LM90	Zhenyu Li , Victor Milenkovic, Constructing strongly convex hulls using exact or rounded arithmetic, Proceedings of the sixth annual symposium on Computational geometry, p.235-243, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98577]
	Mil89	V. Milenkovic. Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic, in Proc. 30th A nnu. IEEE Sympos. Found. Comput. Sci., pages 500-505, 1989.
	She96	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]
	SI89	K. Sugihara , M. Iri, A solid modelling system free from topological inconsistency, Journal of Information Processing, v.12 n.4, p.380-393, 1989
	SI94	K. Sugihara and M. Iri. A robust topologyoriented incremental algorithm for Voronoi diagrams. Internat. J. Comput. Geom. Appl., 4:179-228, 1994.
	Yap93	C.K. Yap. Towards exact geometric computation. In Proc. 5th Canad. Conf. Comput. Geom., pages 405-419, 1993.
	YD95	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 5

	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
	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
	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
	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
	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