TY - JOUR

T1 - Controlled linear perturbation

AU - Sacks, Elisha

AU - Milenkovic, Victor

AU - Kyung, Min Ho

N1 - Funding Information:
The authors thank Eric Fischer, a Purdue undergraduate, for testing the CGAL Minkowski sum software. Milenkovic is supported by NSF grant CCF-0904707 . Sacks is supported by NSF grant CCF-0904832 and by a PLM grant. Kyung is supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science, and Technology, (2010-0012021) .

PY - 2011/10

Y1 - 2011/10

N2 - We present an algorithmic solution to the robustness problem in computational geometry, called controlled linear perturbation, and demonstrate it on Minkowski sums of polyhedra. The robustness problem is how to implement real RAM algorithms accurately and efficiently using computer arithmetic. Approximate computation in floating point arithmetic is efficient but can assign incorrect signs to geometric predicates, which can cause combinatorial errors in the algorithm output. We make approximate computation accurate by performing small input perturbations, which we compute using differential calculus. This strategy supports fast, accurate Minkowski sum computation. The only prior robust implementation uses a less efficient algorithm, requires exact algebraic computation, and is far slower based on our extensive testing.

AB - We present an algorithmic solution to the robustness problem in computational geometry, called controlled linear perturbation, and demonstrate it on Minkowski sums of polyhedra. The robustness problem is how to implement real RAM algorithms accurately and efficiently using computer arithmetic. Approximate computation in floating point arithmetic is efficient but can assign incorrect signs to geometric predicates, which can cause combinatorial errors in the algorithm output. We make approximate computation accurate by performing small input perturbations, which we compute using differential calculus. This strategy supports fast, accurate Minkowski sum computation. The only prior robust implementation uses a less efficient algorithm, requires exact algebraic computation, and is far slower based on our extensive testing.

KW - Perturbation methods

KW - Robust computational geometry

UR - http://www.scopus.com/inward/record.url?scp=80052944586&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052944586&partnerID=8YFLogxK

U2 - 10.1016/j.cad.2011.06.015

DO - 10.1016/j.cad.2011.06.015

M3 - Article

AN - SCOPUS:80052944586

VL - 43

SP - 1250

EP - 1257

JO - CAD Computer Aided Design

JF - CAD Computer Aided Design

SN - 0010-4485

IS - 10

ER -