Given a set P of red points and a set Q of blue points in the plane of total size n, we investigate the problem of finding two disjoint isothetic rectangles containing all the points of Q avoiding any points of P. Such rectangles are called two separating disjoint isothetic rectangles. We fi rst compute two separating disjoint axis-aligned rectangles in O(n log n) time. Then, we relax the axis-aligned constraint and report all combinatorially di erent two separating disjoint isothetic rectangles. To compute these rectangles, we introduce some events by rotating the coordinate system and process these events. Computing and processing all of the events are done in O(n^2 log n) time. Thus, our algorithm reports all combinatorially di erent separating rectangles in O(n^2 log n) time.
Moslehi, Z., & Bagheri, A. (2016). Separating bichromatic point sets by two disjoint isothetic rectangles. Scientia Iranica, 23(3), 1228-1238. doi: 10.24200/sci.2016.3891
MLA
Zahra Moslehi; Alireza Bagheri. "Separating bichromatic point sets by two disjoint isothetic rectangles". Scientia Iranica, 23, 3, 2016, 1228-1238. doi: 10.24200/sci.2016.3891
HARVARD
Moslehi, Z., Bagheri, A. (2016). 'Separating bichromatic point sets by two disjoint isothetic rectangles', Scientia Iranica, 23(3), pp. 1228-1238. doi: 10.24200/sci.2016.3891
VANCOUVER
Moslehi, Z., Bagheri, A. Separating bichromatic point sets by two disjoint isothetic rectangles. Scientia Iranica, 2016; 23(3): 1228-1238. doi: 10.24200/sci.2016.3891
)