### 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 (US) |
---|---|

Title of host publication | Proceedings - IEEE International Symposium on Circuits and Systems |

Publisher | Publ by IEEE |

Pages | 2533-2536 |

Number of pages | 4 |

ISBN (Print) | 0780312813 |

State | Published - Jan 1 1993 |

Event | Proceedings of the 1993 IEEE International Symposium on Circuits and Systems - Chicago, IL, USA Duration: May 3 1993 → May 6 1993 |

### Publication series

Name | Proceedings - IEEE International Symposium on Circuits and Systems |
---|---|

Volume | 4 |

ISSN (Print) | 0271-4310 |

### Other

Other | Proceedings of the 1993 IEEE International Symposium on Circuits and Systems |
---|---|

City | Chicago, IL, USA |

Period | 5/3/93 → 5/6/93 |

### Fingerprint

### ASJC Scopus subject areas

- Electrical and Electronic Engineering

### Cite this

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

}

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 -