On the time complexity for circumscribing a convex polygon

✍ Scribed by Tony C Wood; Hyun-Chan Lee

• Publisher: Elsevier Science
• Year: 1985
• Weight: 68 KB
• Volume: 30
• Category: Article
• ISSN: 0734-189X
• DOI: 10.1016/0734-189x(85)90166-5

✦ Synopsis

A recent article "Circumscribing a Convex Polygon by a Polygon of Fewer Sides with Minimal Area Addition" by Dori and Ben-Bassat, Comput. Vision Graph. Image Process. 24, 1983, 131-159, raised several interesting questions including the time complexity of their algorithm. In this paper, the time complexity on circumscribing an n-gon by an m-gon, where m < n, is analyzed to be O(n lg n).