Finding minimal convex nested polygons

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

doi:10.1016/0890-5401(89)90049-7

Finding minimal convex nested polygons

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

Computer Science

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

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 language	English (US)
Pages (from-to)	98-110
Number of pages	13
Journal	Information and Computation
Volume	83
Issue number	1
DOIs	https://doi.org/10.1016/0890-5401(89)90049-7
State	Published - Oct 1989

ASJC Scopus subject areas

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

Access to Document

10.1016/0890-5401(89)90049-7

Cite this

@article{def8b2b75d9d473eb2c5e42ced1c8c42,

title = "Finding minimal convex nested polygons",

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.",

author = "Alok Aggarwal and Heather Booth and Joseph O'Rourke and Subhash Suri and Yap, {Chee K.}",

note = "Funding Information: supported by NSF Grants by NSF Grant DCR-84-01633.",

year = "1989",

month = oct,

doi = "10.1016/0890-5401(89)90049-7",

language = "English (US)",

volume = "83",

pages = "98--110",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Finding minimal convex nested polygons

AU - Aggarwal, Alok

AU - Booth, Heather

AU - O'Rourke, Joseph

AU - Suri, Subhash

AU - Yap, Chee K.

N1 - Funding Information: supported by NSF Grants by NSF Grant DCR-84-01633.

PY - 1989/10

Y1 - 1989/10

N2 - 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.

AB - 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.

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

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

U2 - 10.1016/0890-5401(89)90049-7

DO - 10.1016/0890-5401(89)90049-7

M3 - Article

AN - SCOPUS:0024751427

SN - 0890-5401

VL - 83

SP - 98

EP - 110

JO - Information and Computation

JF - Information and Computation

IS - 1

ER -

Finding minimal convex nested polygons

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this