### Abstract

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

Pages (from-to) | 274-296 |

Number of pages | 23 |

Journal | Journal of Algorithms |

Volume | 13 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1992 |

### Fingerprint

### Cite this

*Journal of Algorithms*,

*13*(2), 274-296. https://doi.org/10.1016/0196-6774(92)90019-9

}

*Journal of Algorithms*, vol. 13, no. 2, pp. 274-296. https://doi.org/10.1016/0196-6774(92)90019-9

**A general approach to dominance in the plane.** / Berg, de, M.; Carlsson, S.; Overmars, M.H.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - A general approach to dominance in the plane

AU - Berg, de, M.

AU - Carlsson, S.

AU - Overmars, M.H.

PY - 1992

Y1 - 1992

N2 - 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 e 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) e 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.

AB - 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 e 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) e 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.

U2 - 10.1016/0196-6774(92)90019-9

DO - 10.1016/0196-6774(92)90019-9

M3 - Article

VL - 13

SP - 274

EP - 296

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 2

ER -