登入選單

返回Google圖書搜尋

An Efficient Approach to Removing Geometric Degeneracies

Ioannis Z. Emiris

出版	University of California, Berkeley, 1991
URL	http://books.google.com.hk/books?id=CoFLAQAAMAAJ&hl=&source=gbs_api

註釋

We wish to increase the power of an arbitrary geometric algorithm designed for non-degenerate input, by allowing it to execute over arbitrary inputs. This paper describes a deterministic direct perturbation of the input which applies to algorit hms whose branching decisions depend on determinants in the input parameters. We concentrate on four predicates that cover most important algorithms in computational geometry. The method alters the input parameters by infinitesimal amounts to guarantee t hat the perturbed input lies in general position. It is an attractive candidate for practical use, and is considerably simpler as well as more efficient than existing approaches. Specifically, it is the first method with a complexity overhead that is poly nomial in the input size and, in most cases, a small constant. Under our real computation model, the asymptotic complexity remains unaffected; the bit complexity is at worst increased by a factor proportional to d(2+alpha), where d is the dimension of the geometric space of the input objects and alpha an arbitrarily small positive constant. A variation of the perturbation quantities and is even more efficient. Lastly, we illustrate the applicability of our approach.