Finding largest rectangles in convex polygons

Cited 5 time in webofscience Cited 0 time in scopus
  • Hit : 443
  • Download : 0
We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with n vertices. We give exact algorithms that solve these problems in time O(n(3)). We also give (1 - epsilon)-approximation algorithms that take time O(epsilon(-1/2) log n + epsilon(-3/2)).
Publisher
ELSEVIER SCIENCE BV
Issue Date
2016-01
Language
English
Article Type
Article
Keywords

APPROXIMATION

Citation

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.51, pp.67 - 74

ISSN
0925-7721
DOI
10.1016/j.comgeo.2015.08.001
URI
http://hdl.handle.net/10203/207435
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 5 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0