### Abstract

Let A(H) be the arrangement of a set H of n hyperplanes in d-space. A k-flat is a k-dimensional affine subspace of d-space. The zone of a k-flat f with respect to H is the set of all faces in A(H) that intersect f. this paper we study some problems on zones of k-flats. Our most important result is a data structure for point location in the zone of a k-flat. This structure uses O(nd/2++nk+) preprocessing time and space and has a query time of O(log2 n). We also show how to test efficiently whether two flats are visible from each other with respect to a set of hyperplanes. Then point location in m faces in arrangements is studied. Our data structure for this problem has size O(nd/2+md/2/d) and the query time is O(log2 n).

Original language | English |
---|---|

Pages (from-to) | 131-143 |

Number of pages | 13 |

Journal | Computational Geometry |

Volume | 6 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1996 |

## Fingerprint Dive into the research topics of 'Point location in zones of k-flats in arrangements'. Together they form a unique fingerprint.

## Cite this

Berg, de, M., Kreveld, van, M. J., Schwarzkopf, O., & Snoeyink, J. (1996). Point location in zones of k-flats in arrangements.

*Computational Geometry*,*6*(3), 131-143. https://doi.org/10.1016/0925-7721(95)00021-6