A general approach to dominance in the plane

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    15 Citaten (Scopus)

    Samenvatting

    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.
    Originele taal-2Engels
    Pagina's (van-tot)274-296
    Aantal pagina's23
    TijdschriftJournal of Algorithms
    Volume13
    Nummer van het tijdschrift2
    DOI's
    StatusGepubliceerd - 1992

    Vingerafdruk Duik in de onderzoeksthema's van 'A general approach to dominance in the plane'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit