Separating Multi-Color Points on a Plane with Fewest Axis-Parallel Lines

• Autorzy: Majumder S. , Nandy S.C. , Bhattacharya Bhargab.B.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we deal with the problem of partitioning a set of coplanar points of more than one colors into monochromatic cells using minimum number of axis-parallel straight lines. It is first shown that the problem is NP-hard. A fast heuristic is then presented to solve this problem. Experimental results on randomly generated instances indicate that the proposed method is much faster than the existing techniques, with minor degradation in the cost of the partition.

Słowa kluczowe

EN

monochromatic partitioning; NP-hardness; heuristic; vertex cover

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 3
• Strony: 315--324
• Opis fizyczny: Bibliogr. 12 poz., tab.

Twórcy

autor

Majumder S.

autor

Nandy S.C.

autor

Bhattacharya Bhargab.B.

• ACM Unit, ISI, Kolkata 700 108, India,

Bibliografia

• [1] Brooks, R. R., Iyengar, S. S.: Multi-Sensor Fusion: Fundamentals and Applications With Software, Prentice- Hall, 1997.
• [2] Calinescu, G., Dumitrescu A., Wan, P.: Separating points by axis-parallel lines, Proc.Canadian Conf. On Computational Geometry, 2004, 7-10.
• [3] Dumitrescu, A., Pach, J.: Partitioning colored point sets into monochromatic parts, Proc. Workshop on Algorithms and Data Structures, LNCS 2125, 2001, 264-275.
• [4] Gaur, D. R., Ibaraki, T., Krishnamurti, R.: Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem, Journal of Algorithms, 43, 2002, 138-152.
• [5] Hassin, R., Megiddo, N.: Approximation algorithms for hitting objects with straight lines, Discrete Applied Mathematics, 30, 1991, 29-42.
• [6] Tardos, E.: A strongly polynomial algorithm to solve combinatorial linear programs, Operations Research, 34, 1986, 250-256.
• [7] Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.
• [8] Kano, M., Merino, C., Urrutia, J.: On plane spanning trees and cycles of multicolored point sets with few intersections, Information Processing Letters, 93, 2005, 301-306.
• [9] Koushanfar, F., Slijepcevic, S., Potkonjak M., Sangiovanni-Vincentelli, A.: Error-tolerant multi-modal sensor fusion, IEEE CAS Workshop on Wireless Communication and Networking, Pasadena, 2002.
• [10] Lu, B., Xu, Y., Zhu B., Du, D.: On a minimum linear classification problem, Journal of Global Optimization, 26, 2003, 435-441.
• [11] Majumder, S., Bhattacharya B. B., Jafri, S. M. A.: Reducing crossing numbers of multi-color rectilinear steiner trees using monochromatic partitioning, Advances in Computer Science and Engineering: Reports and Monographs, vol. 2: Innovative Applications of Information Technology for the DevelopingWorld (Ed. L. M. Patnaik, et al.), World Scientific, Singapore, July 2007, 73-77.
• [12] Tokunaga, S.: Intersection number of two connected geometric graphs, Information Processing Letters, 59, 1996, 331-333.