FINDING EXTREMAL POLYGONS.

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

doi:10.1137/0214011

FINDING EXTREMAL POLYGONS.

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

Research output: Contribution to journal › Article › peer-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 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 - Jan 1 1985
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Science(all)
Mathematics(all)

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 Paul} and Drysdale, {Robert L.(Scot)} and Guibas, {Leo J.}",

year = "1985",

month = jan,

day = "1",

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 Paul

AU - Drysdale, Robert L.(Scot)

AU - Guibas, Leo J.

PY - 1985/1/1

Y1 - 1985/1/1

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 - http://www.scopus.com/inward/record.url?scp=0022013192&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022013192&partnerID=8YFLogxK

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