非表示:
キーワード:
-
要旨:
Reliable implementation of geometric algorithms is a notoriously difficult
task. Algorithms are usually designed for the Real-RAM, capable of computing
with real numbers in the sense of mathematics, and for non-degenerate inputs.
But, real computers are not Real-RAMs and inputs are frequently degenerate.
In the first part of the talk we illustrate the pitfalls of geometric computing
by way of examples [KMP+04]. The examples demonstrate in a lucid way that
standard and frequently taught algorithms can go completely astray when naively
implemented with floating point arithmetic.
Partially supported by the IST Programme of the EU under Contract No
IST-2005-TODO, Algorithms for Complex Shapes (ACS).