### 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 (eg, 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) |
---|---|

Title of host publication | Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06 |

Publisher | Association for Computing Machinery |

Pages | 386-394 |

Number of pages | 9 |

ISBN (Print) | 1595933409, 9781595933409 |

DOIs | |

State | Published - 2006 |

Event | 22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States Duration: Jun 5 2006 → Jun 7 2006 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|---|

Volume | 2006 |

### Other

Other | 22nd Annual Symposium on Computational Geometry 2006, SCG'06 |
---|---|

Country | United States |

City | Sedona, AZ |

Period | 6/5/06 → 6/7/06 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

### Keywords

- Computational Geometry
- Sublinear algorithms

## Fingerprint Dive into the research topics of 'Online geometric reconstruction'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06*(pp. 386-394). (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006). Association for Computing Machinery. https://doi.org/10.1145/1137856.1137912