On a general method for maximizing and minimizing among certain geometric problems

David P. Dobkin; Lawrence Snyder

doi:10.1109/SFCS.1979.28

On a general method for maximizing and minimizing among certain geometric problems

David P. Dobkin, Lawrence Snyder

Research output: Contribution to journal › Conference article › peer-review

4 Scopus citations

Abstract

Problems concerned with finding inscribing or circumscribing polygons that maximize some measurement are considered such as: Find an area maximizing triangle inscribed in a given convex polygon. Algorithms solving a number of these problems in linear time are presented. They use the common approach of finding an initial solution with respect to a fixed bounding point and then iteratively transforming this solution into a new solution with respect to a new point. The generality of this approach is discussed and several open problems are noted.

Original language	English (US)
Article number	4567996
Pages (from-to)	9-17
Number of pages	9
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs	https://doi.org/10.1109/SFCS.1979.28
State	Published - 1979
Event	20th Annual Symposium on Foundations of Computer Science, FOCS 1979 - San Juan, United States Duration: Oct 29 1979 → Oct 31 1979

All Science Journal Classification (ASJC) codes

General Computer Science

Access to Document

10.1109/SFCS.1979.28

Cite this

@article{aa38e024acb3423293ff44560f4e8c21,

title = "On a general method for maximizing and minimizing among certain geometric problems",

abstract = "Problems concerned with finding inscribing or circumscribing polygons that maximize some measurement are considered such as: Find an area maximizing triangle inscribed in a given convex polygon. Algorithms solving a number of these problems in linear time are presented. They use the common approach of finding an initial solution with respect to a fixed bounding point and then iteratively transforming this solution into a new solution with respect to a new point. The generality of this approach is discussed and several open problems are noted.",

author = "Dobkin, {David P.} and Lawrence Snyder",

note = "Publisher Copyright: {\textcopyright} 1979 IEEE.; 20th Annual Symposium on Foundations of Computer Science, FOCS 1979 ; Conference date: 29-10-1979 Through 31-10-1979",

year = "1979",

doi = "10.1109/SFCS.1979.28",

language = "English (US)",

pages = "9--17",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

}

TY - JOUR

T1 - On a general method for maximizing and minimizing among certain geometric problems

AU - Dobkin, David P.

AU - Snyder, Lawrence

PY - 1979

Y1 - 1979

N2 - Problems concerned with finding inscribing or circumscribing polygons that maximize some measurement are considered such as: Find an area maximizing triangle inscribed in a given convex polygon. Algorithms solving a number of these problems in linear time are presented. They use the common approach of finding an initial solution with respect to a fixed bounding point and then iteratively transforming this solution into a new solution with respect to a new point. The generality of this approach is discussed and several open problems are noted.

AB - Problems concerned with finding inscribing or circumscribing polygons that maximize some measurement are considered such as: Find an area maximizing triangle inscribed in a given convex polygon. Algorithms solving a number of these problems in linear time are presented. They use the common approach of finding an initial solution with respect to a fixed bounding point and then iteratively transforming this solution into a new solution with respect to a new point. The generality of this approach is discussed and several open problems are noted.

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

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

U2 - 10.1109/SFCS.1979.28

DO - 10.1109/SFCS.1979.28

M3 - Conference article

AN - SCOPUS:85068652559

SN - 0272-5428

SP - 9

EP - 17

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

M1 - 4567996

T2 - 20th Annual Symposium on Foundations of Computer Science, FOCS 1979

Y2 - 29 October 1979 through 31 October 1979

ER -

On a general method for maximizing and minimizing among certain geometric problems

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this