A general approach to dominance in the plane

M. Berg, de, S. Carlsson, M.H. Overmars

    Research output: Contribution to journalArticleAcademicpeer-review

    15 Citations (Scopus)


    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.
    Original languageEnglish
    Pages (from-to)274-296
    Number of pages23
    JournalJournal of Algorithms
    Issue number2
    Publication statusPublished - 1992

    Fingerprint Dive into the research topics of 'A general approach to dominance in the plane'. Together they form a unique fingerprint.

    Cite this