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)

    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 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
    Volume13
    Issue number2
    DOIs
    Publication statusPublished - 1992

    Fingerprint

    Visibility
    Data structures
    Query
    Dynamic Data Structures
    Set of points
    Finite Set
    Generalise
    Arbitrary
    Object

    Cite this

    Berg, de, M. ; Carlsson, S. ; Overmars, M.H. / A general approach to dominance in the plane. In: Journal of Algorithms. 1992 ; Vol. 13, No. 2. pp. 274-296.
    @article{86124f80dce0460cb329ae08023728ec,
    title = "A general approach to dominance in the plane",
    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 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.",
    author = "{Berg, de}, M. and S. Carlsson and M.H. Overmars",
    year = "1992",
    doi = "10.1016/0196-6774(92)90019-9",
    language = "English",
    volume = "13",
    pages = "274--296",
    journal = "Journal of Algorithms",
    issn = "0196-6774",
    publisher = "Academic Press Inc.",
    number = "2",

    }

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

    In: Journal of Algorithms, Vol. 13, No. 2, 1992, p. 274-296.

    Research output: Contribution to journalArticleAcademicpeer-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 -