Abstract
We present polynomial time results for computing a minimum separation between two regions in a planar weighted subdivision. Our results are based on a (more general) theorem that characterizes a class of functions for which optimal solutions arise on the boundary of the feasible domain. A direct consequence of this theorem is that a minimum separation goes through a vertex of the weighted subdivision. We also consider extensions and present results for the 3-D case and for a more general case of the 2-D separation problem, in which the separation (link) has associated an ε-width. Our results are the first nontrivial upper bounds for these problems. We also discuss simple approximation algorithms for the 2-D case and present a prune-and-search approach that can be used with either the continuous or the approximate solutions to speed up the computation. We have implemented a variant of the two region minimum separation algorithm based on the prune-and-search scheme.
Original language | English (US) |
---|---|
Pages (from-to) | 33-57 |
Number of pages | 25 |
Journal | International Journal of Computational Geometry and Applications |
Volume | 19 |
Issue number | 1 |
DOIs | |
State | Published - Feb 2009 |
Keywords
- Approximation algorithm
- Minimum separation
- Polynomial time
- Weighted region
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Theory and Mathematics
- Computational Mathematics
- Applied Mathematics