On rectilinear link distance

    Research output: Contribution to journalArticleAcademicpeer-review

    42 Citations (Scopus)

    Abstract

    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.
    Original languageEnglish
    Pages (from-to)13-34
    Number of pages22
    JournalComputational Geometry
    Volume1
    Issue number1
    DOIs
    Publication statusPublished - 1991

    Fingerprint Dive into the research topics of 'On rectilinear link distance'. Together they form a unique fingerprint.

    Cite this