Minimum separation in weighted subdivisions

Ovidiu Daescu, James Palmer

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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 languageEnglish (US)
Pages (from-to)33-57
Number of pages25
JournalInternational Journal of Computational Geometry and Applications
Volume19
Issue number1
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Minimum separation in weighted subdivisions'. Together they form a unique fingerprint.

Cite this