Farthest-point queries with geometric and combinatorial constraints

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

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Abstract

    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(log2 n) time. Our data structure needs O(n log n) 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.
    Original languageEnglish
    Title of host publicationDiscrete and computational geometry : Japanese Conference, JCDCG 2004, Tokyo, Japan, October 8-11, 2004 : revised selected papers
    EditorsJ. Akiyama, M. Kano, X. Tan
    Place of PublicationBerlin
    PublisherSpringer
    Pages62-75
    ISBN (Print)3-540-30467-3
    DOIs
    Publication statusPublished - 2005

    Publication series

    NameLecture Notes in Computer Science
    Volume3742
    ISSN (Print)0302-9743

    Fingerprint Dive into the research topics of 'Farthest-point queries with geometric and combinatorial constraints'. Together they form a unique fingerprint.

  • Cite this

    Daescu, O., Mi, N., Shin, C. S., & Wolff, A. (2005). Farthest-point queries with geometric and combinatorial constraints. In J. Akiyama, M. Kano, & X. Tan (Eds.), Discrete and computational geometry : Japanese Conference, JCDCG 2004, Tokyo, Japan, October 8-11, 2004 : revised selected papers (pp. 62-75). (Lecture Notes in Computer Science; Vol. 3742). Springer. https://doi.org/10.1007/11589440_7