Loading...
Please wait, while we are loading the content...
Similar Documents
Shape fitting with outliers
| Content Provider | CiteSeerX |
|---|---|
| Author | Har-Peled, Sariel Wang, Yusu |
| Abstract | Given a set H of n hyperplanes in IR d, we present an algorithm that ε-approximates the extent between the top and bottom k levels of the arrangement of H in time O(n+(k/ε) c), where c is a constant depending on d. The algorithm relies on computing a subset of H of size O(k/ε d−1), in near linear time, such that the k-level of the arrangement of the subset approximates that of the original arrangement. Using this algorithm, we propose efficient approximation algorithms for shape fitting with outliers for various shapes. This is the first algorithms to handle outliers efficiently for the shape fitting problems considered. 1 |
| File Format | |
| Volume Number | 33 |
| Journal | SIAM J. Comput |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Bottom Level Shape Fitting Problem Linear Time Constant Depending Various Shape First Algorithm Shape Fitting Original Arrangement Efficient Approximation Algorithm Algorithm Relies |
| Content Type | Text |
| Resource Type | Article |
