publication . Preprint . 2013

A deterministic pseudorandom perturbation scheme for arbitrary polynomial predicates

Irving, Geoffrey; Green, Forrest;
Open Access English
  • Published: 08 Aug 2013
Abstract
We present a symbolic perturbation scheme for arbitrary polynomial geometric predicates which combines the benefits of Emiris and Canny's simple randomized linear perturbation scheme with Yap's multiple infinitesimal scheme for general predicates. Like the randomized scheme, our method accepts black box polynomial functions as input. For nonmaliciously chosen predicates, our method is as fast as the linear scheme, scaling reasonably with the degree of the polynomial even for fully degenerate input. Like Yap's scheme, the computed sign is deterministic, never requiring an algorithmic restart (assuming a high quality pseudorandom generator), and works for arbitrar...
Subjects
free text keywords: Computer Science - Computational Geometry, I.3.5, 68U05
Download from
19 references, page 1 of 2

[1] Amenta, N., Choi, S., and Rote, G. Incremental constructions con brio. In Proceedings of the nineteenth annual symposium on Computational geometry (2003), ACM, pp. 211-219.

[2] Brönnimann, H., Burnikel, C., and Pion, S. Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Applied Mathematics 109, 1 (2001), 25-47.

[3] Burnikel, C., Mehlhorn, K., and Schirra, S. On degeneracy in geometric computations. In Proceedings of the fifth annual ACM-SIAM Symposium on Discrete algorithms (1994), Society for Industrial and Applied Mathematics, pp. 16-23.

[4] Devillers, O., Fronville, A., Mourrain, B., and Teillaud, M. Algebraic methods and arithmetic filtering for exact predicates on circle arcs. In Proceedings of the sixteenth annual symposium on Computational geometry (2000), ACM, pp. 139-147.

[5] Devillers, O., Karavelas, M., and Teillaud, M. Qualitative Symbolic Perturbation: a new geometry-based perturbation framework. Rapport de recherche RR-8153, INRIA, 2012.

[6] Edelsbrunner, H., and Mücke, E. P. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics (TOG) 9, 1 (1990), 66-104.

[7] Emiris, I., and Canny, J. An efficient approach to removing geometric degeneracies. In Proceedings of the eighth annual symposium on Computational geometry (1992), ACM, pp. 74-82.

[8] Emiris, I. Z., and Canny, J. F. A general approach to removing degeneracies. SIAM Journal on Computing 24, 3 (1995), 650-664.

[9] Granlund, T., and the GMP development team. GNU MP: The GNU Multiple Precision Arithmetic Library, 5.0.5 ed., 2012. http://gmplib.org.

[10] Halperin, D., and Leiserowitz, E. Controlled perturbation for arrangements of circles. International Journal of Computational Geometry & Applications 14, 04n05 (2004), 277-310.

[11] Halperin, D., and Shelton, C. R. A perturbation scheme for spherical arrangements with application to molecular modeling. Computational Geometry 10, 4 (1998), 273-287. [OpenAIRE]

[12] Neidinger, R. D. Multivariable interpolating polynomials in Newton forms. In Joint Mathematics Meetings 2009 (2009), pp. 5-8.

[13] Olver, P. J. On multivariate interpolation. Studies in Applied Mathematics 116, 2 (2006), 201-240.

[14] Oruç, H., and Phillips, G. M. Explicit factorization of the Vandermonde matrix. Linear Algebra and its Applications 315, 1 (2000), 113-123. [OpenAIRE]

[15] Salmon, J. K., Moraes, M. A., Dror, R. O., and Shaw, D. E. Parallel random numbers: as easy as 1, 2, 3. In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis (New York, NY, USA, 2011), SC '11, ACM, pp. 16:1-16:12.

19 references, page 1 of 2
Abstract
We present a symbolic perturbation scheme for arbitrary polynomial geometric predicates which combines the benefits of Emiris and Canny's simple randomized linear perturbation scheme with Yap's multiple infinitesimal scheme for general predicates. Like the randomized scheme, our method accepts black box polynomial functions as input. For nonmaliciously chosen predicates, our method is as fast as the linear scheme, scaling reasonably with the degree of the polynomial even for fully degenerate input. Like Yap's scheme, the computed sign is deterministic, never requiring an algorithmic restart (assuming a high quality pseudorandom generator), and works for arbitrar...
Subjects
free text keywords: Computer Science - Computational Geometry, I.3.5, 68U05
Download from
19 references, page 1 of 2

[1] Amenta, N., Choi, S., and Rote, G. Incremental constructions con brio. In Proceedings of the nineteenth annual symposium on Computational geometry (2003), ACM, pp. 211-219.

[2] Brönnimann, H., Burnikel, C., and Pion, S. Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Applied Mathematics 109, 1 (2001), 25-47.

[3] Burnikel, C., Mehlhorn, K., and Schirra, S. On degeneracy in geometric computations. In Proceedings of the fifth annual ACM-SIAM Symposium on Discrete algorithms (1994), Society for Industrial and Applied Mathematics, pp. 16-23.

[4] Devillers, O., Fronville, A., Mourrain, B., and Teillaud, M. Algebraic methods and arithmetic filtering for exact predicates on circle arcs. In Proceedings of the sixteenth annual symposium on Computational geometry (2000), ACM, pp. 139-147.

[5] Devillers, O., Karavelas, M., and Teillaud, M. Qualitative Symbolic Perturbation: a new geometry-based perturbation framework. Rapport de recherche RR-8153, INRIA, 2012.

[6] Edelsbrunner, H., and Mücke, E. P. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics (TOG) 9, 1 (1990), 66-104.

[7] Emiris, I., and Canny, J. An efficient approach to removing geometric degeneracies. In Proceedings of the eighth annual symposium on Computational geometry (1992), ACM, pp. 74-82.

[8] Emiris, I. Z., and Canny, J. F. A general approach to removing degeneracies. SIAM Journal on Computing 24, 3 (1995), 650-664.

[9] Granlund, T., and the GMP development team. GNU MP: The GNU Multiple Precision Arithmetic Library, 5.0.5 ed., 2012. http://gmplib.org.

[10] Halperin, D., and Leiserowitz, E. Controlled perturbation for arrangements of circles. International Journal of Computational Geometry & Applications 14, 04n05 (2004), 277-310.

[11] Halperin, D., and Shelton, C. R. A perturbation scheme for spherical arrangements with application to molecular modeling. Computational Geometry 10, 4 (1998), 273-287. [OpenAIRE]

[12] Neidinger, R. D. Multivariable interpolating polynomials in Newton forms. In Joint Mathematics Meetings 2009 (2009), pp. 5-8.

[13] Olver, P. J. On multivariate interpolation. Studies in Applied Mathematics 116, 2 (2006), 201-240.

[14] Oruç, H., and Phillips, G. M. Explicit factorization of the Vandermonde matrix. Linear Algebra and its Applications 315, 1 (2000), 113-123. [OpenAIRE]

[15] Salmon, J. K., Moraes, M. A., Dror, R. O., and Shaw, D. E. Parallel random numbers: as easy as 1, 2, 3. In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis (New York, NY, USA, 2011), SC '11, ACM, pp. 16:1-16:12.

19 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue