On optimal approximation of orthogonal polygons

Yao Ping Chen, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 (US)
Title of host publicationProceedings - IEEE International Symposium on Circuits and Systems
PublisherPubl by IEEE
Pages2533-2536
Number of pages4
ISBN (Print)0780312813
StatePublished - Jan 1 1993
Externally publishedYes
EventProceedings of the 1993 IEEE International Symposium on Circuits and Systems - Chicago, IL, USA
Duration: May 3 1993May 6 1993

Publication series

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

Other

OtherProceedings of the 1993 IEEE International Symposium on Circuits and Systems
CityChicago, IL, USA
Period5/3/935/6/93

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

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

Cite this