### Abstract

This paper investigates the existence of linear space data structures for range searching. We examine the homothetic range search problem, where a set S of n points in the plane is to be preprocessed so that for any triangle T with sides parallel to three fixed directions the points of S that lie in T can be computed efficiently. We also look at domination searching in three dimensions. In this problem, S is a set of n points in E^{3} and the question is to retrieve all points of S that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and near-optimal in the second.

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

Title of host publication | Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986 |

Publisher | Association for Computing Machinery, Inc |

Pages | 293-302 |

Number of pages | 10 |

ISBN (Electronic) | 0897911946, 9780897911948 |

DOIs | |

State | Published - Aug 1 1986 |

Externally published | Yes |

Event | 2nd Annual Symposium on Computational Geometry, SCG 1986 - Yorktown Heights, United States Duration: Jun 2 1986 → Jun 4 1986 |

### Publication series

Name | Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986 |
---|

### Other

Other | 2nd Annual Symposium on Computational Geometry, SCG 1986 |
---|---|

Country | United States |

City | Yorktown Heights |

Period | 6/2/86 → 6/4/86 |

### All Science Journal Classification (ASJC) codes

- Geometry and Topology
- Theoretical Computer Science
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Linear space data structures for two types of range search'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986*(pp. 293-302). (Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986). Association for Computing Machinery, Inc. https://doi.org/10.1145/10515.10547