On Computing General Position Views of Data in Three Dimensions

✍ Scribed by Francisco Gómez; Suneeta Ramaswami; Godfried Toussaint

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 224 KB
• Volume: 13
• Category: Article
• ISSN: 1047-3203
• DOI: 10.1006/jvci.2001.0503

✦ Synopsis

Several degeneracies in spatial data can be removed (without perturbing the input) by a global rigid transformation of the input. Such degeneracies are called extrinsic degeneracies. The removal of extrinsic degeneracies is referred to as "computing a general-position view" in the graphics and visualization community, which may be described as a view that minimizes loss of information due to degeneracies. In this paper, we address a general approach for removing extrinsic degeneracies by suitably transforming the input. Such an approach has received little attention in the computational geometry literature on computing in the presence of degeneracies. Existing methods for removing degeneracies in computational geometry can be classified as either approximation or perturbation methods. These methods give the implementer two rather unsatisfactory choices: find an approximate solution to the original problem given, or find an exact solution to an approximation of the original problem. In contrast to these approaches, if the problem at hand requires the removal of extrinsic degeneracies only, our approach allows an exact solution to the original problem even when the input is in fact degenerate. Once the solution is obtained on the transformed nondegenerate input, it can be transformed back trivially to yield the solution to the original problem. We consider several nondegeneracy assumptions that are typically made in the literature, propose algorithms for performing the