TY - GEN

T1 - Towards Soft Exact Computation (Invited Talk)

AU - Yap, Chee

N1 - Funding Information:
This work is supported by NSF Grants CCF-1423228 and CCF-1564132.

PY - 2019

Y1 - 2019

N2 - Exact geometric computation (EGC) is a general approach for achieving robust numerical algorithms that satisfy geometric constraints. At the heart of EGC are various Zero Problems, some of which are not-known to be decidable and others have high computational complexity. Our current goal is to introduce notions of “soft- correctness” in order to avoid Zero Problems. We give a bird’s eye view of our recent work with collaborators in two principle areas: computing zero sets and robot path planning. They share a common Subdivision Framework. Such algorithms (a) have adaptive complexity, (b) are practical, and (c) are effective. Here, “effective algorithm” means it is easily and correctly implementable from standardized algorithmic components. Our goals are to outline these components and to suggest new components to be developed. We discuss a systematic pathway to go from the abstract algorithmic description to an effective algorithm in the subdivision framework.

AB - Exact geometric computation (EGC) is a general approach for achieving robust numerical algorithms that satisfy geometric constraints. At the heart of EGC are various Zero Problems, some of which are not-known to be decidable and others have high computational complexity. Our current goal is to introduce notions of “soft- correctness” in order to avoid Zero Problems. We give a bird’s eye view of our recent work with collaborators in two principle areas: computing zero sets and robot path planning. They share a common Subdivision Framework. Such algorithms (a) have adaptive complexity, (b) are practical, and (c) are effective. Here, “effective algorithm” means it is easily and correctly implementable from standardized algorithmic components. Our goals are to outline these components and to suggest new components to be developed. We discuss a systematic pathway to go from the abstract algorithmic description to an effective algorithm in the subdivision framework.

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

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

U2 - 10.1007/978-3-030-26831-2_2

DO - 10.1007/978-3-030-26831-2_2

M3 - Conference contribution

AN - SCOPUS:85071445752

SN - 9783030268305

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 12

EP - 36

BT - Computer Algebra in Scientific Computing - 21st International Workshop, CASC 2019, Proceedings

A2 - England, Matthew

A2 - Sadykov, Timur M.

A2 - Seiler, Werner M.

A2 - Koepf, Wolfram

A2 - Vorozhtsov, Evgenii V.

PB - Springer Verlag

T2 - 21st International Workshop on Computer Algebra in Scientific Computing, CASC 2019

Y2 - 26 August 2019 through 30 August 2019

ER -