TY - GEN
T1 - Towards Soft Exact Computation (Invited Talk)
AU - Yap, Chee
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
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 -