Farthest-point queries with geometric and combinatorial constraints

O. Daescu, N. Mi, C.S. Shin, A. Wolff

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    13 Citaten (Scopus)


    In this paper we discuss farthest-point problems in which a set or sequence S of n points in the plane is given in advance and can be preprocessed to answer various queries efficiently. First, we give a data structure that can be used to compute the point farthest from a query line segment in O(log2n) time. Our data structure needs O(nlogn) space and preprocessing time. To the best of our knowledge no solution to this problem has been suggested yet. Second, we show how to use this data structure to obtain an output-sensitive query-based algorithm for polygonal path simplification. Both results are based on a series of data structures for fundamental farthest-point queries that can be reduced to each other.
    Originele taal-2Engels
    Pagina's (van-tot)174-185
    TijdschriftComputational Geometry
    Nummer van het tijdschrift3
    StatusGepubliceerd - 2006


    Duik in de onderzoeksthema's van 'Farthest-point queries with geometric and combinatorial constraints'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit