FINDING EXTREMAL POLYGONS.

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

Research output: Contribution to journalArticlepeer-review

59 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