Given n points in the plane, the authors present algorithms for finding maximum perimeter or area convex k-gons with vertices k of the given n points. The algorithms work in linear space and time O(kn lg n plus n lg**2 n). for the special case k equals 3 they give O(n lg n) algorithms for these problems. Several related issues are discussed.
|Original language||English (US)|
|Number of pages||14|
|Journal||SIAM Journal on Computing|
|State||Published - Jan 1 1985|
All Science Journal Classification (ASJC) codes
- Computer Science(all)