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

David P. Dobkin, Lawrence Snyder

Research output: Contribution to journalConference article

2 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 languageEnglish (US)
Article number4567996
Pages (from-to)9-17
Number of pages9
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - Jan 1 1979
Externally publishedYes
Event20th Annual Symposium on Foundations of Computer Science, FOCS 1979 - San Juan, United States
Duration: Oct 29 1979Oct 31 1979

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this