On rectilinear link distance

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    44 Citaten (Scopus)


    In this paper we study two link distance problems for rectilinear paths inside a simple rectilinear polygon P. First, we present a data structure using O(n log n) storage such that a shortest path between two query points can be computed efficiently. If both query points are vertices of P, the query time is O(1 + l), where l is the number of links. If the query points are arbitrary points inside P, then the query time becomes O(log n + l). The resulting path is not only optimal in the rectilinear link metric, but it is optimal in the L1-metric as well. Secondly, it is shown that the rectilinear link diameter of P can be computed in time O(n log n). We also give an approximation algorithm that runs in linear time. This algorithm produces a solution that differs by at most three links from the exact diameter. The solutions are based on a rectilinear version of Chazelle's polygon cutting theorem. This new theorem states that any simple rectilinear polygon can be cut into two rectilinear subpolygons of size at most times the original size, and that such a cut segment can be found in linear time.
    Originele taal-2Engels
    Pagina's (van-tot)13-34
    Aantal pagina's22
    TijdschriftComputational Geometry
    Nummer van het tijdschrift1
    StatusGepubliceerd - 1991


    Duik in de onderzoeksthema's van 'On rectilinear link distance'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit