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

Externally published | Yes |

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.