Approximation of convex figures by pairs of rectangles

We consider the problem of approximating a convex figure in the plane by a pair (r,R) of homothetic (that is, similar and parallel) rectangles with r subset of or equal to C subset of or equal to R, We show the existence of such a pair where the sides of the outer rectangle are at most twice as long as the sides of the inner rectangle, thereby solving a problem posed by Polya and Szego. If the n vertices of a convex polygon C are given as a sorted array, such an approximating pair of rectangles can be computed in time O(log(2)n). (C) 1998 Elsevier Science B.V.
Publisher
ELSEVIER SCIENCE BV
Issue Date
1998-05
Language
ENG
Keywords

BODIES

Citation

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.10, no.2, pp.77 - 87

ISSN
0925-7721
DOI
10.1016/S0925-7721(96)00019-3
URI
http://hdl.handle.net/10203/321
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
sfrw-acfpr-98.pdf(226.34 kB)Download
  • Hit : 700
  • Download : 627
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 6 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0