FINDING EXTREMAL POLYGONS.

James E. Boyce, David Paul Dobkin, Robert L.(Scot) Drysdale, Leo J. Guibas

Research output: Contribution to journalArticle

53 Scopus citations

Abstract

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 languageEnglish (US)
Pages (from-to)134-147
Number of pages14
JournalSIAM Journal on Computing
Volume14
Issue number1
DOIs
StatePublished - Jan 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'FINDING EXTREMAL POLYGONS.'. Together they form a unique fingerprint.

  • Cite this

    Boyce, J. E., Dobkin, D. P., Drysdale, R. L. S., & Guibas, L. J. (1985). FINDING EXTREMAL POLYGONS. SIAM Journal on Computing, 14(1), 134-147. https://doi.org/10.1137/0214011