Can I read Point Location in Zones of K-flats in Arrangements on EtoBox?

Point Location in Zones of K-flats in Arrangements by Mark de Berg; Marc van Kreveld; Otfried Schwarzkopf; Jack Snoeyink is a Computer Science article available to read on EtoBox.

What is Point Location in Zones of K-flats in Arrangements about?

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. In 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 [a/2j+E + 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/2J+eT~ [d/zl/d) and the query time is O(log 2 n).

Who reads Point Location in Zones of K-flats in Arrangements?

Author

Mark de Berg; Marc van Kreveld; Otfried Schwarzkopf; Jack Snoeyink

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0925-7721)

Published

1996

Language

EN

Field

Computer Science (Physical Sciences)