Name
Abstract | ||
|---|---|---|
Given two points p and q and a (finite) set of points O in the plane, p is said to dominate q with respect to O if p dominates q and there is no o ϵ O such that p dominates o and o dominates q. In other words, O is a set of obstacles that might block the “rectangular view” from p to q. Given sets P and O we are interested in determining all pairs (p, q) ϵ P × P such that p dominates q with respect to O. This generalizes notions of direct dominance and rectangular visibility that have been studied before. An algorithm is presented that solves the problem in optimal time O(n log n + k), where n is the size of P ∪ O and k is the number of answers. We also study query versions of the problem in which we ask for all points that are dominated with respect to O by a given query point. Both static and dynamic data structures are presented. Finally, the notion of dominance with respect to obstacles is extended to obstacle sets that may contain arbitrary objects. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0196-6774(92)90019-9 | Journal of Algorithms |
Keywords | DocType | Volume |
general approach | Journal | 13 |
Issue | ISSN | Citations |
2 | 0196-6774 | 9 |
PageRank | References | Authors |
0.79 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark T. de Berg | 1 | 19 | 6.74 |
| Svante Carlsson | 2 | 764 | 90.17 |
| Mark H. Overmars | 3 | 4572 | 518.80 |