Abstract
We investigate a new class of geometric problems based on the idea of online error correction. Suppose one is given access to a large geometric dataset though a query mechanism; for example, the dataset could be a terrain and a query might ask for the coordinates of a particular vertex or for the edges incident to it. Suppose, in addition, that the dataset satisfies some known structural property P (for example, monotonicity or convexity) but that, because of errors and noise, the queries occasionally provide answers that violate P. Can one design a filter that modifies the query's answers so that (i) the output satisfies P; (ii) the amount of data modification is minimized? We provide upper and lower bounds on the complexity of online reconstruction for convexity in 2D and 3D.
| Original language | English (US) |
|---|---|
| Article number | 14 |
| Journal | Journal of the ACM |
| Volume | 58 |
| Issue number | 4 |
| DOIs | |
| State | Published - Jul 1 2011 |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
Keywords
- Computational geometry
- Sublinear algorithms