Finding minimal convex nested polygons

Alok Aggarwal, Heather Booth, Joseph O'Rourke, Subhash Suri, Chee K. Yap

Research output: Contribution to journalArticle

Abstract

We consider the problem of finding a polygon nested between two given convex polygons that has a minimal number of vertices. Our main result is an O(n log k) algorithm for solving the problem, where n is the total number of vertices of the given polygons, and k is the number of vertices of a minimal nested polygon. We also present an O(n) sub-optimal algorithm, and a simple O(nk) optimal algorithm.

Original languageEnglish (US)
Pages (from-to)98-110
Number of pages13
JournalInformation and Computation
Volume83
Issue number1
DOIs
StatePublished - Oct 1989

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Finding minimal convex nested polygons'. Together they form a unique fingerprint.

  • Cite this