Loading...
Please wait, while we are loading the content...
Similar Documents
An Efficient Approach to Removing Geometric Degeneracies (Extended Abstract) (1992)
| Content Provider | CiteSeerX |
|---|---|
| Author | Emiris, Ioannis |
| Abstract | Our aim is to perturb the input so that an algorithm designed under the hypothesis of input non-degeneracy can execute on arbitrary instances. The deterministic scheme of [EmCa] was the first efficient method and was applied to two important predicates. Here it is extended in a consistent manner to another two common predicates, thus making it valid for most algorithms in computational geometry. It is shown that this scheme incurs no extra algebraic complexity over the original algorithm while it increases the bit complexity by a factor roughly proportional to the dimension of the geometric space. The second contribution of this paper is a variant scheme for a restricted class of algorithms that is asymptotically optimal with respect to the algebraic as well as the bit complexity. Both methods are simple to implement and require no symbolic computation. They also conform to certain criteria ensuring that the solution to the original input can be restored from the output on the perturbed input. This is immediate when the input to solution mapping obeys a continuity property and requires some case-specific work otherwise. Finally we discuss extensions and limitations to our approach. |
| File Format | |
| Publisher Date | 1992-01-01 |
| Access Restriction | Open |
| Subject Keyword | Variant Scheme Bit Complexity Important Predicate Original Input Continuity Property First Efficient Method Original Algorithm Consistent Manner Extra Algebraic Complexity Symbolic Computation Efficient Approach Geometric Space Extended Abstract Case-specific Work Input Non-degeneracy Second Contribution Computational Geometry Restricted Class Removing Geometric Degeneracy Perturbed Input Common Predicate Arbitrary Instance Certain Criterion Deterministic Scheme |
| Content Type | Text |
| Resource Type | Article |
