Point location in zones of k-flats in arrangements

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...

Full description

Saved in:
Bibliographic Details
Published in:Computational geometry : theory and applications 1996-06, Vol.6 (3), p.131-143
Main Authors: de Berg, Mark, van Kreveld, Marc, Schwarzkopf, Otfried, Snoeyink, Jack
Format: Article
Language:English
Subjects:
Arrangements
Implicit point location
k-flats
Multidimensional parametric search
Zones
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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(n ⌊ d 2 ⌋+ε +n k+ε) preprocessing time and space and has a query time of O(log 2 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(n ⌊ d 2 ⌋+ε m ⌈ d 2 ⌉ d ) and the query time is O(log 2 n).
ISSN:0925-7721
DOI:10.1016/0925-7721(95)00021-6