A note on lower bounds for the maximum area and maximum perimeter k-gon problems

Robert L.(Scot) Drysdale; Jerzy W. Jaromczyk

doi:10.1016/0020-0190(89)90022-7

A note on lower bounds for the maximum area and maximum perimeter k-gon problems

Robert L.(Scot) Drysdale, Jerzy W. Jaromczyk

Computer Science

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

6 Scopus citations

Abstract

An Ω(n log n) lower bound time complexity in the computational tree model for the maximum area and maximum perimeter k-gon problems is demonstrated. The proof uses a reduction to the set-disjointness problem and is based on extremal properties of regular polygons.

Original language	English
Pages (from-to)	301-303
Number of pages	3
Journal	Information Processing Letters
Volume	32
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(89)90022-7
State	Published - Oct 3 1989

Keywords

Lower bounds
computational geometry
isoperimetric problems
the computation tree model

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(89)90022-7

Cite this

@article{19caa35781f449c7af9d9df737826af1,

title = "A note on lower bounds for the maximum area and maximum perimeter k-gon problems",

abstract = "An Ω(n log n) lower bound time complexity in the computational tree model for the maximum area and maximum perimeter k-gon problems is demonstrated. The proof uses a reduction to the set-disjointness problem and is based on extremal properties of regular polygons.",

keywords = "Lower bounds, computational geometry, isoperimetric problems, the computation tree model",

author = "Drysdale, {Robert L.(Scot)} and Jaromczyk, {Jerzy W.}",

year = "1989",

month = oct,

day = "3",

doi = "10.1016/0020-0190(89)90022-7",

language = "English",

volume = "32",

pages = "301--303",

number = "6",

}

TY - JOUR

T1 - A note on lower bounds for the maximum area and maximum perimeter k-gon problems

AU - Drysdale, Robert L.(Scot)

AU - Jaromczyk, Jerzy W.

PY - 1989/10/3

Y1 - 1989/10/3

N2 - An Ω(n log n) lower bound time complexity in the computational tree model for the maximum area and maximum perimeter k-gon problems is demonstrated. The proof uses a reduction to the set-disjointness problem and is based on extremal properties of regular polygons.

AB - An Ω(n log n) lower bound time complexity in the computational tree model for the maximum area and maximum perimeter k-gon problems is demonstrated. The proof uses a reduction to the set-disjointness problem and is based on extremal properties of regular polygons.

KW - Lower bounds

KW - computational geometry

KW - isoperimetric problems

KW - the computation tree model

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

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

U2 - 10.1016/0020-0190(89)90022-7

DO - 10.1016/0020-0190(89)90022-7

M3 - Article

AN - SCOPUS:0024960721

SN - 0020-0190

VL - 32

SP - 301

EP - 303

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

A note on lower bounds for the maximum area and maximum perimeter k-gon problems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this