### Abstract

The paper consists of two major parts. In the first part, we re-examine relative ε-approximations, previously studied in [12, 13, 18, 25], and their relation to certain geometric problems, most notably to approximate range counting. Wegive a simple constructive proof of their existence in general range spaces with finite VC dimension, and of a sharp bound on their size, close to the best known one. We then give a construction of smaller-size relative ε-approximations for range spaces that involve points and halfspaces in two and higher dimensions. The planar construction is based on a new structure-spanning trees with small relative crossing number, which we believe to be of independent interest. In the second part, we consider the approximate halfspace range-counting problem in Rd with relative error ε, and show that relative ε-approximations, combined with the shallow partitioning data structures of Matouŝek, yields ef- ficient solutions to this problem. For example, one of our data structures requires linear storage and O(n1+δ) preprocessingtime, for any > 0, and answers a query in time O(ε-n1-1/bd/2c2b log n), for any > 2/bd/2c; the choice of and affects b and the implied constants. Several variants and extensions are also discussed.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07 |

Pages | 327-336 |

Number of pages | 10 |

DOIs | |

State | Published - 2007 |

Event | 23rd Annual Symposium on Computational Geometry, SCG'07 - Gyeongju, Korea, Republic of Duration: Jun 6 2007 → Jun 8 2007 |

### Publication series

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

### Other

Other | 23rd Annual Symposium on Computational Geometry, SCG'07 |
---|---|

Country | Korea, Republic of |

City | Gyeongju |

Period | 6/6/07 → 6/8/07 |

### Keywords

- Approximate range queries
- Discrepancy
- Epsilon-approximations
- Halfspaces
- Partition trees
- Queries
- Range
- Range spaces
- VC-dimension

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

## Fingerprint Dive into the research topics of 'On approximate halfspace range counting and relative epsilon-approximations'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07*(pp. 327-336). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1247069.1247128