A geometric consistency theorem for a symbolic perturbation scheme. (English) Zbl 0705.68056
Summary: 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. We introduce the concept of an infinitesimal perturbation and show that our method is consistent relative to such perturbations.
MSC:
| 68W10 | Parallel algorithms in computer science |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68W30 | Symbolic computation and algebraic computation |
References:
| [1] | Buchberger, B., Gröbner Bases: An algorithmic method in polynomial ideal theory, (Bose, N. K., Recent Trends in Multidimensional Systems Theory (1985), Reidel: Reidel Dordrecht) · Zbl 0587.13009 |
| [2] | Monma, C.; Paterson, M.; Suri, S.; Yao, F. F., Computing Euclidean maximum spanning trees, (4th ACM Symp. on Comput. Geom. (1988)), 241-251 |
| [3] | Charnes, A., Optimality and degeneracy in linear programming, Econometrica, 20, No.2, 160-170 (1952) · Zbl 0049.37903 |
| [4] | Chvátal, V., Linear Programming (1983), Freeman: Freeman San Francisco · Zbl 0318.05002 |
| [5] | Dubt, T.; Mishra, B.; Yap, C. K., Admissible Orderings and Bounds for Grobner Bases Normal Form Algorithm, (Report 88 (1986), NYU-Courant Robotics Lab) |
| [6] | Edelsbrunner, H., Edge-skeletons in arrangements with applications, Algorithmica, 1, 93-110 (1986) · Zbl 0623.68059 |
| [7] | Edelsbrunner, H.; Mücke, E. P., Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms, (4th ACM Symp. on Computational Geometry (1988)), 118-133 |
| [8] | Edelsbrunner, H.; Waupotitsch, R., Computing a ham-sandwich cut in two dimensions, J. Symbolic Comput., 2, 171-178 (1986) · Zbl 0623.68058 |
| [9] | Mishra, B.; Yap, C. K., Notes on Grobner Bases, (Report 87 (1986), NYU-Courant Robotics Lab) · Zbl 0686.13005 |
| [10] | J. Inform. Sci., in press.; J. Inform. Sci., in press. |
| [11] | Papadimitriou, C.; Steiglitz, K., Combinatorial Optimization (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060 |
| [12] | Robbiano, L., On the theory of graded structures, J. Symbolic Comput., 2, 139-170 (1986) · Zbl 0609.13007 |
| [13] | Robbiano, L., Term orderings on the polynomial ring, (EUROCAL ’85, Lecture Notes in Computer Science, No. 20 (1985)), 513-517 · Zbl 0584.13016 |
| [14] | Yap, C. K., Symbolic treatment of geometric degeneracies, (Lecture Notes in Control and Information Sciences, Vol. 113 (1988), Springer-Verlag: Springer-Verlag New York/Berlin), 348-358 · Zbl 0685.65006 |
| [15] | J. Symbolic Comput., in press.; J. Symbolic Comput., in press. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
