FINDING EXTREMAL POLYGONS.

James E. Boyce; David P. Dobkin; Robert L.(Scot) Drysdale; Leo J. Guibas

doi:10.1137/0214011

FINDING EXTREMAL POLYGONS.

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

Research output: Contribution to journal › Article › peer-review

65 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 language	English (US)
Pages (from-to)	134-147
Number of pages	14
Journal	SIAM Journal on Computing
Volume	14
Issue number	1
DOIs	https://doi.org/10.1137/0214011
State	Published - 1985

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1137/0214011

Cite this

@article{45fbeeea5af2422b90f5d0dc194f388c,

title = "FINDING EXTREMAL POLYGONS.",

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.",

author = "Boyce, \{James E.\} and Dobkin, \{David P.\} and Drysdale, \{Robert L.(Scot)\} and Guibas, \{Leo J.\}",

year = "1985",

doi = "10.1137/0214011",

language = "English (US)",

volume = "14",

pages = "134--147",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - FINDING EXTREMAL POLYGONS.

AU - Boyce, James E.

AU - Dobkin, David P.

AU - Drysdale, Robert L.(Scot)

AU - Guibas, Leo J.

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0022013192

UR - https://www.scopus.com/pages/publications/0022013192#tab=citedBy

U2 - 10.1137/0214011

DO - 10.1137/0214011

M3 - Article

AN - SCOPUS:0022013192

SN - 0097-5397

VL - 14

SP - 134

EP - 147

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 1

ER -

FINDING EXTREMAL POLYGONS.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this