Largest Red-Blue Separating Rectangles Study

Largest 
Red
-
Blue
 Separating
Rectangles
Bogdan Armaselu
, 
Ovidiu Daescu
,
Chenglin Fan 
and 
Benjamin Raichel
University of Texas at Dallas
Largest Red-Blue Separating Rectangle
Original problem
Given:
n
 red points 
R
m
 blue points 
B
Goal: find largest area
axis-aligned 
B
-empty
rectangle that contains 
R
(called 
largest red-blue
separating rectangle
)
Our contributions
We consider
extensions of the
original problem
Blue Rectangles
problem
Given n red points 
R
and 
m
 AA (
possibly
intersecting
)
rectangles 
B
Goal is to find largest
area rectangle
containing all red
points and not
intersecting any AA
rectangle
O(
m 
log
 m + n
) 
time
Our contributions
Outliers Problem
Given n red points R
and m blue points B
and an integer 
k
Goal is to find the
largest area rectangle
enclosing 
R
 and
containing <= 
k
 blue
points (“outliers”)
O(poly(
k
)
 
m 
log
 m 
+
 n
)
time
Motivation
Tumor separation
Want to separate
tumor from non-
tumor in a given
radiological H&E-
stained image
Red points denote
tumor cells, blue
points (and
rectangles) denote
healthy cells and
surrounding tissue
Related work
Nandy et al (1990) [4]
Find 
all
 maximal 
empty
 rectangles (MER) among axis-
aligned 
non-intersecting
 rectangles
O(
n 
log
 n + r
) time, where 
r
 is the number of MERs
Nandy et al (1994) [3]
Find 
one
 largest 
empty
 rectangle among arbitrary 
non-
intersecting
 obstacles (such as sticks and polygons)
O(
n 
log
2
 n
) time
Also show how to find empty rectangle inside polygon
Related Work
Sharir et al (2012) [2]
Find largest empty rectangle among a point set 
P
 that contains only a
query point 
q
O(
n 
log
4
 n
) 
time pre-processing
O(log
4
 n
)
 time query
Given q and set B, finds max area
rectangle in 
O(
m
 log 
m
) 
time
Given q and staircase for B, finds
max area rectangle in 
O(m 
α
(m))
time
Original Problem
Find largest 
B
-empty
rectangle enclosing 
R
The lines defining 
S
min
 divide
the plane into 9 regions:
S
min
, 
E, NE, N, NW, W, SW, S
,
and 
SE
For each such region 
r
, let
B
r
 denote the set of blue
points located in 
r
Extend 
S
min
 in each direction
until it touches a blue point
in each of E, N, W and S
Denote by 
S
max
 the resulting
rectangle
 
S
min
 
E
 
 
NE
 
N
 
NW
 
W
 
SW
 
S
 
SE
Original Problem
Definition
. For 
p, q 
ϵ
 
NE
, 
p
 
dominates
 
q
 if x(
p
) > x(
q
), y(
p
) > y(
q
)
The definition can be applied to other quadrants by swapping inequalities
A rectangle enclosing R is 
B
NE 
-empty if its NE corner does not dominate any
points from 
B
NE
The 
staircase 
ST(
NE
) of 
B
NE
: the NE boundary of region not dominating any
blue point in 
B
NE
The largest red-blue separating rectangle is the largest rectangle containing
S
min
 and not containing any point of any of the four staircases
Original 
 Staircase
The original problem reduces to the 
Staircase Problem
,
stated as follows.
Given AA rectangles 
S
min
, 
S
max
, with 
S
min
 contained in 
S
max
, and a
staircase for each quadrant defined by 
S
min
Goal is to find the largest area rectangle 
S*
 containing 
S
min 
and not
containing any point of any staircase.
 
We solve Staircase Problem in 
O(
t
)
 time, where 
t
 is the
complexity of the staircase
Removed 
α
(t) 
factor
Since 
t
 = O(
m
) and computing ST() takes O(
m
 log 
m
) time,
we solve Original Problem in O(
m
 log 
m
 + 
n
) time
Blue Rectangle Problem
Want largest rectangle enclosing 
R
while avoiding AA rectangles in 
B
Blue Rectangle 
 Original
For side regions, e.g. 
E
, for each
rectangle 
r
 intersecting 
E
:
consider an arbitrary point 
p
 
ϵ
 E
 on the
left side of 
r
note that a rectangle enclosing 
S
min
intersects 
r
 iff it contains p
For corner regions, e.g. 
NE
, for each
rectangle r crossing 
NE
:
consider corner 
q
 of 
r
, such that 
q
 
ϵ
 
NE
and 
q
 does not dominate any point of 
r
note that a rectangle enclosing 
S
min
intersects 
r
 iff its 
NE 
corner 
p
 dominates 
q
Let 
B’ 
be the resulting “blue” point set
Solve Original Problem on 
R
 and 
B’
Outliers Problem
Want largest rectangle containing 
R
 and <= 
k
 blue
points
There are O(
k
7
) ways to partition k into integers 
k
E
,
…, 
k
SE
 s.t. 
k
E
 + … + 
k
SE
 = 
k
For each such partition, we find the largest
rectangle that encloses  
S
min
 and contains 
k
E
 
points
from 
E
, 
k
NE
 from 
NE
, etc.
From each side region, e.g. 
E
, we take the 
 
 
(
k
E
 
+1)-th leftmost point in 
B
E
Outliers Problem
Denote by ST
k
(
P
) the 
k-th
level staircase of P
, i.e.
chain of points
dominating exactly 
k
points in 
P
From each corner region,
e.g. 
NE
, we find ST
k
(
B
NE
)
Outliers Problem
Lemma 1
. For any set 
P
 of 
m
 points and any integer
k, there exists a set 
Q
 of O(
m
) points such that
ST
k
(
P
) = ST(
Q
). Moreover, ST
k
(
P
) can be computed
in O(
m
 log 
m
) time
Proof (sketch).
- There are two types of points that can be in 
Q
Points 
p
 in 
P 
that dominate 
k
 points in 
P
Points 
q
 not in 
P
 but with either the same X coordinate or the
same Y coordinate as some point 
r
 in 
P 
(“breakpoints”) s.t. 
q
dominates 
k
 points in 
P
- Thus, the points in ST(
Q
) dominate exactly
 k 
points in 
P
,
i.e. ST(
Q
) = ST
k
(
P
)
Outliers Problem
O(
m
) points in 
P
 dominate 
k
 other points in 
P
In a staircase, for each X coordinate of a point, there is at
most one breakpoint
Hence O(
m
) breakpoints, so |
Q
| = O(
m
)
To compute ST
k
(
P
), sweep a vertical line from 
S
min
 to the
right
Maintain the points in 
P
 seen so far, along with # points
they dominate, in a balanced BST sorted by Y
Outliers Problem
Each point 
p
 in 
P
 induces
an “event” on ST
k
(
P
)
Based on Y(
p
) and the
contents of BST, can
determine the number 
t
 of
points that 
p
 dominates in
O(log 
m
) time
If 
t = k
, then add p to ST
k
(
P
)
Outliers Problem
Else, if there exist points q, r s.t. r is on
ST(P) and q is highest below r to the
left of l, then s is a breakpoint, where
X(s) = X(p), Y(s) = Y(q)
q
, 
r 
and 
s
 can be found in O(log 
m
) time
There are O(
m
) events and we
spend O(log 
m
) for each, so 
 
 
O(
m
 log 
m
) in total
To solve the k-Outlier Problem for a
given quadrant, find the k-th level
staircase of the quadrant, then solve
the Staircase Problem
Conclusion
Theorem 2
. Blue Rectangle Problem can be solved in
time 
O(m 
log
 m + n
) 
and space 
O(
m + n
)
Theorem 3
.  Outliers Problem can be solved in time
O(
m 
log
 m + n
)
 with 
O(
m + n
) 
space for a given
partition 
 
k
E
 + … + 
k
SE
 = 
k
Reduction to Staircase Problem
This gives O(
k
7
 
m
 log 
m + n
) overall
Open problems
Faster approach for the outlier case (want to avoid
treating all possible partitions of k, thus avoiding the
O(k^7) factor)
Replace AA rectangles in B with other shapes (circles,
polygons, etc)
Find largest arbitrary oriented rectangle among
different shapes
Largest circle among different shapes
References
[1] B. Armaselu and O. Daescu. Maximum Area Rectangle
Separating Red and Blue Points. CCCG’2016: 244-251
[2] 
H. Kaplan, S. Mozes, Y. Nussbaum, and 
M. Sharir.
Submatrix maximum queries in monge matrices and monge
partial matrices, and their applications. 23
rd
 Annual ACM-
SIAM Symposium on Discrete Algorithms: 338-355, 2012.
[3] S.C Nandy, A. Sinha, and B.B. Bhattacharya. Location of
the largest empty rectangle among arbitrary obstacles.
Foundations of Software Technology and 
Theoretical
Computer Science: 159-170, 1994.
[4] 
S. C Nandy, B. B. Bhattacharya and S. Ray. Efficient
algorithms for identifying all maximal isothetic empty
rectangles in VLSI layout design. 
FSTTCS 1990
: 255-269
Slide Note
Embed
Share

This study explores the problem of finding the largest area axis-aligned B-empty rectangle containing n red points and m blue points. The research discusses various extensions to the original problem, such as the Blue Rectangles problem and the Outliers Problem, aiming to achieve efficient solutions with time complexities outlined. The motivation behind the research includes applications in tumor separation in radiological images, where red points represent tumor cells and blue points represent healthy cells and tissue. Related work on finding maximal empty rectangles and largest empty rectangles among point sets is also discussed.


Uploaded on Sep 30, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Largest Red-Blue Separating Rectangles Bogdan Armaselu, Ovidiu Daescu, Chenglin Fan and Benjamin Raichel University of Texas at Dallas

  2. Largest Red-Blue Separating Rectangle Original problem Given: n red points R m blue points B Goal: find largest area axis-aligned B-empty rectangle that contains R (called largest red-blue separating rectangle)

  3. Our contributions We consider extensions of the original problem Blue Rectangles problem Given n red points R and m AA (possibly intersecting) rectangles B Goal is to find largest area rectangle containing all red points and not intersecting any AA rectangle O(m log m + n) time

  4. Our contributions Outliers Problem Given n red points R and m blue points B and an integer k Goal is to find the largest area rectangle enclosing R and containing <= k blue points ( outliers ) O(poly(k) m log m + n) time

  5. Motivation Tumor separation Want to separate tumor from non- tumor in a given radiological H&E- stained image Red points denote tumor cells, blue points (and rectangles) denote healthy cells and surrounding tissue

  6. Related work Nandy et al (1990) [4] Find all maximal empty rectangles (MER) among axis- aligned non-intersecting rectangles O(n log n + r) time, where r is the number of MERs Nandy et al (1994) [3] Find one largest empty rectangle among arbitrary non- intersecting obstacles (such as sticks and polygons) O(n log2n) time Also show how to find empty rectangle inside polygon

  7. Related Work Sharir et al (2012) [2] Find largest empty rectangle among a point set P that contains only a query point q O(n log4n) time pre-processing O(log4n) time query Given q and set B, finds max area rectangle in O(m log m) time Given q and staircase for B, finds max area rectangle in O(m (m)) time

  8. Original Problem Find largest B-empty rectangle enclosing R The lines defining Smin divide the plane into 9 regions: Smin, E, NE, N, NW, W, SW, S, and SE For each such region r, let Br denote the set of blue points located in r Extend Smin in each direction until it touches a blue point in each of E, N, W and S Denote by Smax the resulting rectangle NW N NE Smin E W SW S SE

  9. Original Problem Definition. For p, q NE, pdominatesq if x(p) > x(q), y(p) > y(q) The definition can be applied to other quadrants by swapping inequalities A rectangle enclosing R is BNE -empty if its NE corner does not dominate any points from BNE The staircase ST(NE) of BNE: the NE boundary of region not dominating any blue point in BNE The largest red-blue separating rectangle is the largest rectangle containing Smin and not containing any point of any of the four staircases

  10. Original Staircase The original problem reduces to the Staircase Problem, stated as follows. Given AA rectangles Smin, Smax, with Smin contained in Smax, and a staircase for each quadrant defined by Smin Goal is to find the largest area rectangle S* containing Smin and not containing any point of any staircase. We solve Staircase Problem in O(t) time, where t is the complexity of the staircase Removed (t) factor Since t = O(m) and computing ST() takes O(m log m) time, we solve Original Problem in O(m log m + n) time

  11. Blue Rectangle Problem Want largest rectangle enclosing R while avoiding AA rectangles in B Blue Rectangle Original For side regions, e.g. E, for each rectangle r intersecting E: consider an arbitrary point p E on the left side of r note that a rectangle enclosing Smin intersects r iff it contains p For corner regions, e.g. NE, for each rectangle r crossing NE: consider corner q of r, such that q NE and q does not dominate any point of r note that a rectangle enclosing Smin intersects r iff its NE corner p dominates q Let B be the resulting blue point set Solve Original Problem on R and B

  12. Outliers Problem Want largest rectangle containing R and <= k blue points There are O(k7) ways to partition k into integers kE, , kSE s.t. kE+ + kSE = k For each such partition, we find the largest rectangle that encloses Smin and contains kEpoints from E, kNE from NE, etc. From each side region, e.g. E, we take the (kE+1)-th leftmost point in BE

  13. Outliers Problem Denote by STk(P) the k-th level staircase of P, i.e. chain of points dominating exactly k points in P From each corner region, e.g. NE, we find STk(BNE)

  14. Outliers Problem Lemma 1. For any set P of m points and any integer k, there exists a set Q of O(m) points such that STk(P) = ST(Q). Moreover, STk(P) can be computed in O(m log m) time Proof (sketch). - There are two types of points that can be in Q Points p in P that dominate k points in P Points q not in P but with either the same X coordinate or the same Y coordinate as some point r in P ( breakpoints ) s.t. q dominates k points in P - Thus, the points in ST(Q) dominate exactly k points in P, i.e. ST(Q) = STk(P)

  15. Outliers Problem O(m) points in P dominate k other points in P In a staircase, for each X coordinate of a point, there is at most one breakpoint Hence O(m) breakpoints, so |Q| = O(m) To compute STk(P), sweep a vertical line from Smin to the right Maintain the points in P seen so far, along with # points they dominate, in a balanced BST sorted by Y

  16. Outliers Problem Each point p in P induces an event on STk(P) Based on Y(p) and the contents of BST, can determine the number t of points that p dominates in O(log m) time If t = k, then add p to STk(P)

  17. Outliers Problem Else, if there exist points q, r s.t. r is on ST(P) and q is highest below r to the left of l, then s is a breakpoint, where X(s) = X(p), Y(s) = Y(q) q, r and s can be found in O(log m) time There are O(m) events and we spend O(log m) for each, so O(m log m) in total To solve the k-Outlier Problem for a given quadrant, find the k-th level staircase of the quadrant, then solve the Staircase Problem

  18. Conclusion Theorem 2. Blue Rectangle Problem can be solved in time O(m log m + n) and space O(m + n) Theorem 3. Outliers Problem can be solved in time O(m log m + n) with O(m + n) space for a given partition kE+ + kSE = k Reduction to Staircase Problem This gives O(k7m log m + n) overall

  19. Open problems Faster approach for the outlier case (want to avoid treating all possible partitions of k, thus avoiding the O(k^7) factor) Replace AA rectangles in B with other shapes (circles, polygons, etc) Find largest arbitrary oriented rectangle among different shapes Largest circle among different shapes

  20. References [1] B. Armaselu and O. Daescu. Maximum Area Rectangle Separating Red and Blue Points. CCCG 2016: 244-251 [2] H. Kaplan, S. Mozes, Y. Nussbaum, and M. Sharir. Submatrix maximum queries in monge matrices and monge partial matrices, and their applications. 23rd Annual ACM- SIAM Symposium on Discrete Algorithms: 338-355, 2012. [3] S.C Nandy, A. Sinha, and B.B. Bhattacharya. Location of the largest empty rectangle among arbitrary obstacles. Foundations of Software Technology and Theoretical Computer Science: 159-170, 1994. [4] S. C Nandy, B. B. Bhattacharya and S. Ray. Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design. FSTTCS 1990: 255-269

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#