Finding extremal polygons

James E. Boyce, David P. Dobkin, Robert L. Drysdale, Leo J. Guibas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

Abstract

Given n points in the plane, we present algorithms for rinding maximum perimeter or area convex k-gons with vertices k of the given n points. Our algorithms work in linear space and time O(kn lgn + n lg2n). For the special case k = 3 we give O(n lg n) algorithms for these problems. Several related issues arc discussed.

Original languageEnglish (US)
Title of host publicationProceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982
PublisherAssociation for Computing Machinery
Pages282-289
Number of pages8
ISBN (Print)0897910702
DOIs
StatePublished - May 5 1982
Event14th Annual ACM Symposium on Theory of Computing, STOC 1982 - San Francisco, United States
Duration: May 5 1982May 7 1982

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other14th Annual ACM Symposium on Theory of Computing, STOC 1982
CountryUnited States
CitySan Francisco
Period5/5/825/7/82

All Science Journal Classification (ASJC) codes

  • Software

Cite this