Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951315 | Journal of Discrete Algorithms | 2017 | 9 Pages |
Abstract
We give a dynamic programming algorithm that solves the MSC problem exactly on monotone orthogonal polygons in O(n) time, improving the 2-approximation algorithm of Katz and Morgenstern (2011). More generally, our algorithm can be used to solve the MSC problem in O(n) time on simple orthogonal polygons P for which the dual graph induced by the vertical decomposition of P is a path. Our results provide the first polynomial-time exact algorithms for the MSC problem on a non-trivial subclass of orthogonal polygons.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mark de Berg, Stephane Durocher, Saeed Mehrabi,