On optimal approximation of orthogonal polygons

Yao Ping Chen, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review


In this paper we consider the following problem in computational geometry which has applications in VLSI floorplan design and image processing. Given an orthogonal polygon P (i.e. edges are either vertical or horizontal) with n vertices and a positive integer m<n, determine an orthogonal polygon Q with less than or equal to m vertices such that ERROR(P, Q) is minimized, where ERROR(P, Q) is defined as the area of the symmetric difference of the interiors of the two polygons. We present a polynomial time optimal algorithm to solve this problem for convex orthogonal polygons. Our algorithm is based on a transformation of the polygon approximation problem into a constrained shortest path problem.

Original languageEnglish
Title of host publication1993 IEEE International Symposium on Circuits and Systems (ISCAS)
Number of pages4
ISBN (Print)0780312813
Publication statusPublished - 6 May 1993
Event1993 IEEE International Symposium on Circuits and Systems (ISCAS) - Chicago, United States
Duration: 3 May 19936 May 1993

Publication series

NameProceedings - IEEE International Symposium on Circuits and Systems (ISCAS)
ISSN (Print)0271-4310


Conference1993 IEEE International Symposium on Circuits and Systems (ISCAS)
Country/TerritoryUnited States
Internet address

Scopus Subject Areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'On optimal approximation of orthogonal polygons'. Together they form a unique fingerprint.

Cite this