A deterministic pseudorandom perturbation scheme for arbitrary polynomial predicates

Geoffrey Irving, Forrest GreenarXiv 2013 · arXiv

Introduction

In computational geometry, "degeneracies"—such as perfectly collinear points or cocyclic vertices—are a primary cause of algorithmic failure. Most geometric algorithms are designed under the assumption of "general position," where such cases do not occur. When an algorithm encounters a degeneracy, mathematical predicates (e.g., determining if a point lies inside a circle) return zero, leading to ambiguity, infinite loops, or system crashes.

To address this, engineers often employ symbolic perturbation, which mathematically "nudges" inputs by infinitesimal amounts to break ties. However, existing methods face a trade-off: deterministic schemes like Yap’s can be exponentially slow for complex predicates, while randomized schemes like Emiris and Canny’s require complex "restart" logic if a nudge fails. This paper introduces a deterministic pseudorandom perturbation scheme that combines the robustness of theoretical models with the performance of randomized approaches, all while remaining a "black box" for the user.

Methodology

The proposed method utilizes an infinite sequence of infinitesimals $(\epsilon_1, \epsilon_2, \dots)$ paired with deterministic pseudorandom vectors $(y_1, y_2, \dots)$. Key components include:

  1. Deterministic Pseudorandomness: By using the Threefry random number generator with a fixed seed or one derived from the input, the "random" nudge becomes deterministic. The same input always yields the same perturbed result, ensuring consistency.
  2. Infinite Series Evaluation: The sign of a polynomial $f(x + \delta)$ is evaluated. If the initial nudge does not break the tie, the algorithm proceeds to the next infinitesimal in the sequence.
  3. Black Box Integration: The scheme treats predicates as black boxes. It uses multivariate polynomial interpolation to recover coefficients needed to determine the sign, avoiding the need to know the internal structure of geometric equations.
  4. Singular Limits: For geometric constructions, the method uses l’Hôpital’s rule to compute limits as the perturbation approaches zero, ensuring exactly rounded output coordinates.

Experimental Evaluation

The authors evaluated the scheme using synthetic benchmarks designed to trigger worst-case degeneracies.

Delaunay Triangulation

Testing involved $n$ normally distributed points versus $n$ points collapsed at the origin. As shown in the performance scaling plots, the algorithm maintains its $O(n \log n)$ complexity even under full degeneracy. While the perturbation overhead makes the degenerate case approximately 13 to 15.5 times slower than the random case, it provides a constant-factor guarantee of robustness.

Performance scaling and resulting mesh for Delaunay triangulation of degenerate point sets.

Circular Arc Boolean Operations

For more complex predicates (degree 6 or 8) involving circular arc "4-gons," the slowdown for degenerate cases ranged from 65 to 252 times. Despite this increase, the method successfully handled configurations that typically crash standard floating-point implementations. The scaling remains predictable, as evidenced by the consistent slopes in the log-log performance plots.

Performance scaling and complex arrangement for circular arc predicates.

Discussion and Future Work

A key insight of this work is the $O(d^3)$ expected cost for a polynomial of degree $d$, a significant improvement over the exponential scaling of previous general-purpose deterministic schemes. By embedding the perturbation logic within the predicate, the outer geometric algorithm remains simple and unaware of the underlying complexity.

However, the performance gap for high-degree predicates remains a challenge. Future work may explore "finite jittering" as a fast first-pass heuristic, using symbolic perturbation only as a fail-safe. Additionally, while the scheme is thread-safe, the timing variance between fast and slow predicate evaluations could impact load balancing in parallel environments like GPUs. Automating the derivation of optimized polynomials from raw inequalities is also a priority for future development.

Summary updated

BibTeX
@misc{irving2013deterministic,
  author = {Geoffrey Irving and Forrest Green},
  title = {{A deterministic pseudorandom perturbation scheme for arbitrary polynomial predicates}},
  year = {2013},
  eprint = {1308.1986},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1308.1986},
}
Figure