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(łog^2 n)$
time. Our data structure needs $O(n 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.
%0 Journal Article
%1 dmsw-fpqgc-06
%A Daescu, Ovidiu
%A Mi, Ningfang
%A Shin, Chan-Su
%A Wolff, Alexander
%D 2006
%J Computational Geometry: Theory and Applications
%K data_structure farthest-point_queries line-segment_queries myown polygonal_path_simplification
%N 3
%P 174--185
%R 10.1016/j.comgeo.2005.07.002
%T Farthest-Point Queries with Geometric and
Combinatorial Constraints
%V 33
%X 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(łog^2 n)$
time. Our data structure needs $O(n 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.
@article{dmsw-fpqgc-06,
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(\log^2 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.},
added-at = {2024-04-29T21:12:31.000+0200},
author = {Daescu, Ovidiu and Mi, Ningfang and Shin, Chan-Su and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/29f6318c5d1f0a077cfd3bb3967f42f23/awolff},
doi = {10.1016/j.comgeo.2005.07.002},
interhash = {796571af72bb6b17532061ab39384f6a},
intrahash = {9f6318c5d1f0a077cfd3bb3967f42f23},
journal = {Computational Geometry: Theory and Applications},
keywords = {data_structure farthest-point_queries line-segment_queries myown polygonal_path_simplification},
number = 3,
pages = {174--185},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/dmsw-fpqgc-06.pdf},
succeeds = {dmsw-fpqgc-05},
timestamp = {2024-04-29T21:12:31.000+0200},
title = {Farthest-Point Queries with Geometric and
Combinatorial Constraints},
volume = 33,
year = 2006
}