Abstract:
|
One of the tasks of Computer-Aided Design/Computer-Aided Manufacturing
is to transform an object's technical drawing - in which geometry is
described by distances and angles - into precise coordinates of the
object's points and lines. One of the best ways of finding these
coordinates is by using step-by-step geometric constructions (e.g.,
ruler-and-compass constructions). These constructions are easy to
implement if we start with exact geometric information (distances and
angles). In practice, however, all technical drawings have tolerances,
so instead of requiring the exact values of distance and angles, we
only require that they stay within prescribed intervals. Different
values within these intervals lead to different coordinates of the
corresponding points. In this paper, we show that the problem of
computing the intervals of possible values of these coordinates is
computationally complicated (NP-hard). Crudely speaking, this means
that it is not possible to have an algorithm for constructing the
endpoints of the corresponding coordinate intervals in feasible time. |