Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient Perturbations for Handling Geometric Degeneracies (1997)
| Content Provider | CiteSeerX |
|---|---|
| Author | Emiris, Ioannis Z. Canny, John F. Seidel, Raimund |
| Abstract | . This article defines input perturbations so that an algorithm designed under certain restrictions on the input can execute on arbitrary instances. A syntactic definition of perturbations is proposed and certain properties are specified under which an algorithm executed on perturbed input produces an output from which the exact answer can be recovered. A general framework is adopted for linear perturbations, which are efficient from the point of view of worst-case complexity. The deterministic scheme of Emiris and Canny [1] was the first efficient scheme and is extended in a consistent manner, most notably to the InSphere primitive. We introduce a variant scheme, applicable to a restricted class of algorithms, which is almost optimal in terms of algebraic as well as bit complexity. Neither scheme requires any symbolic computation and both are simple to use as illustrated by our implementation of a convex hull algorithm in arbitrary dimension. Empirical results and a concrete applicati... |
| File Format | |
| Volume Number | 19 |
| Journal | Algorithmica |
| Language | English |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Geometric Degeneracy Efficient Perturbation Variant Scheme Exact Answer Input Perturbation Certain Restriction Deterministic Scheme General Framework Concrete Applicati Syntactic Definition Linear Perturbation Worst-case Complexity Symbolic Computation Consistent Manner Arbitrary Instance Convex Hull Algorithm Arbitrary Dimension Bit Complexity Empirical Result First Efficient Scheme Certain Property Restricted Class |
| Content Type | Text |
| Resource Type | Article |
