Journal article
Linear approximation of simple objects
Information processing letters, Vol.62(2), pp.89-94
1997
DOI: 10.1016/S0020-0190(97)00049-5
Abstract
Let
P =
P
1, P
2, …, P
m be a set of
m convex polygons in the plane with a total number of
n vertices, and for 1 ⩽
i ⩽
m, let
w
i
gE
R
+ be a weight associated with
P
i
. The weighted distance between a line
l and a polygon
P
i
is given by
d(
l,
P
i
) =
min
pϵP
i
,
qϵl
d(
p,
q).
w
i
, where
d(
p,
q) is the Euclidean distance between
p and
q. We want to compute a line
l that minimizes the maximum distance between
l and the polygons of
P. We present an O(
nα(
n)
log
3
n)-time algorithm to compute such a line. We also give an O(
n
2+
ε
)-time algorithm, where ε is an arbitrarily small positive constant, to solve the three dimensional version of this problem; here,
P is a set of convex polytopes in R
3, and we want to compute a plane
h that minimizes the maximum weighted distance between
h and the polytopes.
Details
- Title: Subtitle
- Linear approximation of simple objects
- Creators
- Kasturi R Varadarajan - Duke UniversityPankaj K Agarwal - Duke University
- Resource Type
- Journal article
- Publication Details
- Information processing letters, Vol.62(2), pp.89-94
- Publisher
- Elsevier B.V
- DOI
- 10.1016/S0020-0190(97)00049-5
- ISSN
- 0020-0190
- eISSN
- 1872-6119
- Language
- English
- Date published
- 1997
- Academic Unit
- Computer Science
- Record Identifier
- 9984259478702771
Metrics
9 Record Views