LARGEST PLACEMENT OF ONE CONVEX POLYGON INSIDE ANOTHER

Authors
AGARWAL PK AMENTA N SHARIR M
Citation
Pk. Agarwal et al., LARGEST PLACEMENT OF ONE CONVEX POLYGON INSIDE ANOTHER, Discrete & computational geometry, 19(1), 1998, pp. 95-104
Citations number
16
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
19
Issue
1
Year of publication
1998
Pages
95 - 104
Database
ISI
SICI code
0179-5376(1998)19:1<95:LPOOCP>2.0.ZU;2-B
Abstract
We show that the largest similar copy of a convex polygon P with m edg es inside a convex polygon Q with n edges can be computed in O(mn(2) l og n) time. We also show that the combinatorial complexity of the spac e of all similar copies of P inside Q is O(mn(2)), and that it can als o be computed in O(mn(2) log n) time.