Skip to search boxSkip to navigationSkip to main content

Farthest-point queries with geometric and combinatorial constraints

  • O. Daescu
    ,
  • N. Mi
    ,
  • C.S. Shin
    ,
  • A. Wolff
Output:
Contribution to journal
Article
Academic
Peer-review

Information

Output type

Output:
Contribution to journal
Article
Academic
Peer-review

Original language

English

Pages from-to (Number of pages)

Pages 174-185

Journal (Volume, Issue Number)

Computational Geometry (Volume 33, Issue 3)

Publication milestones

  • Published - 2006

Publication status

Published - 2006

ISSN

0925-7721

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(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.

Metrics

Metrics

SciVal
FWCI
1.49
SciVal
Author count
4
SciVal
Paper percentile
80
SciVal
citations
18
Scopus
citations
18

PlumX, opens in new tab

Captures
10
Citation count
18