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

Fingerprint

Computational geometry
Image processing
Polynomials

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Chen, Y. P., & Wong, D. F. (1993). On optimal approximation of orthogonal polygons. In Proceedings - IEEE International Symposium on Circuits and Systems (pp. 2533-2536). (Proceedings - IEEE International Symposium on Circuits and Systems; Vol. 4). Publ by IEEE.

On optimal approximation of orthogonal polygons. / Chen, Yao Ping; Wong, D. F.

Proceedings - IEEE International Symposium on Circuits and Systems. Publ by IEEE, 1993. p. 2533-2536 (Proceedings - IEEE International Symposium on Circuits and Systems; Vol. 4).

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

Chen, YP & Wong, DF 1993, On optimal approximation of orthogonal polygons. in Proceedings - IEEE International Symposium on Circuits and Systems. Proceedings - IEEE International Symposium on Circuits and Systems, vol. 4, Publ by IEEE, pp. 2533-2536, Proceedings of the 1993 IEEE International Symposium on Circuits and Systems, Chicago, IL, USA, 5/3/93.
Chen YP, Wong DF. On optimal approximation of orthogonal polygons. In Proceedings - IEEE International Symposium on Circuits and Systems. Publ by IEEE. 1993. p. 2533-2536. (Proceedings - IEEE International Symposium on Circuits and Systems).
Chen, Yao Ping ; Wong, D. F. / On optimal approximation of orthogonal polygons. Proceedings - IEEE International Symposium on Circuits and Systems. Publ by IEEE, 1993. pp. 2533-2536 (Proceedings - IEEE International Symposium on Circuits and Systems).
@inproceedings{7112a0ceee95467cbd746544df2283ff,
title = "On optimal approximation of orthogonal polygons",
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",
author = "Chen, {Yao Ping} and Wong, {D. F.}",
year = "1993",
month = "1",
day = "1",
language = "English (US)",
isbn = "0780312813",
series = "Proceedings - IEEE International Symposium on Circuits and Systems",
publisher = "Publ by IEEE",
pages = "2533--2536",
booktitle = "Proceedings - IEEE International Symposium on Circuits and Systems",

}

TY - GEN

T1 - On optimal approximation of orthogonal polygons

AU - Chen, Yao Ping

AU - Wong, D. F.

PY - 1993/1/1

Y1 - 1993/1/1

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:0027261708

SN - 0780312813

T3 - Proceedings - IEEE International Symposium on Circuits and Systems

SP - 2533

EP - 2536

BT - Proceedings - IEEE International Symposium on Circuits and Systems

PB - Publ by IEEE

ER -