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 | |
| 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 |
Scopus Subject Areas
- Electrical and Electronic Engineering