摘要: Many applications like picture processing, data compression or pattern recognition require a covering of set points most often located in the (discrete) plane by rectangles due to some cost constraints. In this paper we provide exact dynamic programming algorithms for point sets regular rectangles, that have obey certain boundary conditions. The objective function is minimize sum area, circumference and number patches used. This may be motivated requirements numerically solving PDE’s discretization over (adaptive multi-)grids.
springer.com
springerlink.com参考文章(10)
Stefan Porschen, On the rectangular subset closure of point sets international conference on computational science and its applications. pp. 796- 805 ,(2005) , 10.1007/11424758_82
Peter Bastian, Load Balancing for Adaptive Multigrid Methods SIAM Journal on Scientific Computing. ,vol. 19, pp. 1303- 1321 ,(1998) , 10.1137/S1064827596297562
Steven J. Plimpton, Bruce Hendrickson, James R. Stewart, A parallel rendezvous algorithm for interpolation between multiple grids Journal of Parallel and Distributed Computing. ,vol. 64, pp. 266- 276 ,(2004) , 10.1016/J.JPDC.2003.11.006
John Hershberger, Subhash Suri, Finding tailored partitions Journal of Algorithms. ,vol. 12, pp. 431- 463 ,(1991) , 10.1016/0196-6774(91)90013-O
Steven S Skiena, Probing Convex polygons with half-planes Journal of Algorithms. ,vol. 12, pp. 359- 374 ,(1991) , 10.1016/0196-6774(91)90009-N
Dorit S. Hochba, Approximation Algorithms for NP-Hard Problems ,(1996)
J.C. Culberson, R.A. Reckhow, Covering polygons is hard foundations of computer science. ,vol. 17, pp. 601- 611 ,(1988) , 10.1109/SFCS.1988.21976
Stefan Porschen, On Covering Z-Grid Points by Rectangles Electronic Notes in Discrete Mathematics. ,vol. 8, pp. 80- 83 ,(2001) , 10.1016/S1571-0653(05)80086-1
Felipe C. Calheiros, Abilio Lucena, Cid C. de Souza, Optimal rectangular partitions Networks. ,vol. 41, pp. 51- 67 ,(2003) , 10.1002/NET.10058
Steven L. Tanimoto, Robert J. Fowler, COVERING IMAGE SUBSETS WITH PATCHES. NATO Conference Series, (Series) 4: Marine Sciences. ,vol. 2, pp. 835- 839 ,(1980)