A geometric consistency theorem for a symbolic perturbation scheme

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A geometric consistency theorem for a symbolic perturbation scheme

Full text

Pdf (659 KB)

Source

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

Urbana-Champaign, Illinois, United States

Pages: 134 - 142

Year of Publication: 1988

ISBN:0-89791-270-5

Author

C. K. Yap

Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 25, Citation Count: 13

Additional Information:

abstract 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/73393.73407 What is a DOI?

ABSTRACT

In a previous paper, we introduced a generic solution to the problem of data degeneracy in geometric algorithms. The scheme is simple to use: algorithms qualifying under our requirements just have to use a prescribed blackbox for polynomial evaluation in order to achieve a symbolic perturbation of data. In this paper, we introduce the concept of an infinitesimal perturbation and show that our method is consistent relative to such perturbations.

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	B. Buchberger. Multidimensional systems theory, chapter GrSbner: An algorithmic method in polynomial ideal theory. D. Reidel Publishing Company, 1985.
	2	A. Charnes. Optimality and degeneracy in linear programming. Econometrica, 20(2):160-170, 1952.
	3	V. Chv~tal. Linear Programming. W. H. Freeman and Company, 1983.
	4	T. Dub4, B. Mishra, and C. K. Yap. Admissible orderings and bounds for Gr6bner bases normal form algorithm. Report 88, NYU- Courant Robotics Lab., 1986.
	5	H. Edelsbrunner, Edge-skeletons in arrangements with applications, Algorithmica, v.1 n.1, p.93-109, Jan. 1986 [doi>10.1007/BF01840438]
	6	H. Edelsbrunner and Ernst t~eter Miicke. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. Report No. UIUCDCS-R-87-1393, Dept. of Comp. Sci., Univ. of Illinois at Urbana-Champaign, December 1987.
	7	H. Edelsbrunner , R. Waupotitsch, Computing a ham-sandwich cut in two dimensions, Journal of Symbolic Computation, v.2 n.2, p.171-178, June 1986 [doi>10.1006/jsco.1998.0247]
	8	Bud Mishra , Chee Yap, Notes on Grobner bases, Information Sciences: an International Journal, v.48 n.3, p.219-252, Aug. 1989 [doi>10.1016/0020-0255(89)90037-6]
	9	Lorenzo Robbiano, On the theory of graded structures, Journal of Symbolic Computation, v.2 n.2, p.139-170, June 1986 [doi>10.1006/jsco.1996.0006]
	10	Lorenzo Robbiano, Term Orderings on the Polynominal Ring, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.513-517, April 01-03, 1985
	11	Chee K. Yap. Symbolic treatment of geometric degeneracies. In Proceedings 13th IFIP Conference on System Modelling and Optimization, Chuo University, Tokyo, Aug 31-Sep 4, 1987. to appear, Lecture Notes in Computer Science.

CITED BY 13

	Mark Segal, Using tolerances to guarantee valid polyhedral modeling results, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.105-114, Aug. 1990
	J. E. Goodman , R. Pollack , B. Sturmfels, Coordinate representation of order types requires exponential storage, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.405-410, May 14-17, 1989, Seattle, Washington, United States
	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
	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
	K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, 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
	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
	D. Salesin , J Stolfi , L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proceedings of the fifth annual symposium on Computational geometry, p.208-217, June 05-07, 1989, Saarbruchen, West Germany
	Xiaohong Zhu , Shiaofen Fang , Beat D. Brüderlin, Obtaining robust Boolean set operations for manifold solids by avoiding and eliminating redundancy., Proceedings on the second ACM symposium on Solid modeling and applications, p.147-154, May 19-21, 1993, Montreal, Quebec, Canada
	Christoph M. Hoffmann, The Problems of Accuracy and Robustness in Geometric Computation, Computer, v.22 n.3, p.31-40, March 1989
	V. Milenkovic, Calculating approximate curve arrangements using rounded arithmetic, Proceedings of the fifth annual symposium on Computational geometry, p.197-207, June 05-07, 1989, Saarbruchen, West Germany
	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
	David Eppstein, Testing bipartiteness of geometric intersection graphs, ACM Transactions on Algorithms (TALG), v.5 n.2, p.1-35, March 2009