On optimal approximation of orthogonal polygons

Yao Ping Chen; D. F. Wong

doi:10.1109/ISCAS.1993.394281

On optimal approximation of orthogonal polygons

Yao Ping Chen
, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

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 language	English
Title of host publication	1993 IEEE International Symposium on Circuits and Systems (ISCAS)
Publisher	IEEE
Pages	2533-2536
Number of pages	4
ISBN (Print)	0780312813
DOIs	https://doi.org/10.1109/ISCAS.1993.394281
Publication status	Published - 6 May 1993
Event	1993 IEEE International Symposium on Circuits and Systems (ISCAS) - Chicago, United States Duration: 3 May 1993 → 6 May 1993 https://ieeexplore.ieee.org/xpl/conhome/1067/proceeding

Publication series

Name	Proceedings - IEEE International Symposium on Circuits and Systems (ISCAS)
Volume	4
ISSN (Print)	0271-4310

Conference

Conference	1993 IEEE International Symposium on Circuits and Systems (ISCAS)
Country/Territory	United States
City	Chicago
Period	3/05/93 → 6/05/93
Internet address	https://ieeexplore.ieee.org/xpl/conhome/1067/proceeding

Access to Document

10.1109/ISCAS.1993.394281

Cite this

@inproceedings{edc40b65badf44ffae0a10e2d3e9ba0d,

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 = may,

day = "6",

doi = "10.1109/ISCAS.1993.394281",

language = "English",

isbn = "0780312813",

series = "Proceedings - IEEE International Symposium on Circuits and Systems (ISCAS)",

publisher = "IEEE",

pages = "2533--2536",

booktitle = "1993 IEEE International Symposium on Circuits and Systems (ISCAS)",

address = "United States",

note = "1993 IEEE International Symposium on Circuits and Systems (ISCAS) ; Conference date: 03-05-1993 Through 06-05-1993",

url = "https://ieeexplore.ieee.org/xpl/conhome/1067/proceeding",

}

Chen, YP & Wong, DF 1993, On optimal approximation of orthogonal polygons. in 1993 IEEE International Symposium on Circuits and Systems (ISCAS). Proceedings - IEEE International Symposium on Circuits and Systems (ISCAS), vol. 4, IEEE, pp. 2533-2536, 1993 IEEE International Symposium on Circuits and Systems (ISCAS), Chicago, Illinois, United States, 3/05/93. https://doi.org/10.1109/ISCAS.1993.394281

TY - GEN

T1 - On optimal approximation of orthogonal polygons

AU - Chen, Yao Ping

AU - Wong, D. F.

PY - 1993/5/6

Y1 - 1993/5/6

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 - https://www.scopus.com/pages/publications/0027261708

U2 - 10.1109/ISCAS.1993.394281

DO - 10.1109/ISCAS.1993.394281

M3 - Conference proceeding

AN - SCOPUS:0027261708

SN - 0780312813

T3 - Proceedings - IEEE International Symposium on Circuits and Systems (ISCAS)

SP - 2533

EP - 2536

BT - 1993 IEEE International Symposium on Circuits and Systems (ISCAS)

PB - IEEE

T2 - 1993 IEEE International Symposium on Circuits and Systems (ISCAS)

Y2 - 3 May 1993 through 6 May 1993

ER -

On optimal approximation of orthogonal polygons

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this