# Exercise 14.3.7

$\star$ VLSI databases commonly represent an integrated circuit as a list of rectangles. Assume that each rectangle is rectilinearly oriented (sides parallel to the x- and y-axes), so that we represent a rectangle by its minimum and maximum x- and y-coordinates. Give an $\O(n \lg n)$-time algorithm to decide whether or not a set of $n$ rectangles so represented contains two rectangles that overlap. Your algorithm need not report all intersecting pairs, but it must report that an overlap exists if one rectangle entirely covers another, even if the boundary lines do not intersect. (Hint: Move a "sweep" line across the set of rectangles.)

This bears similarity to Exercise 14.1-8, only we need an interval tree, instead of a order statistic tree.

The algorithm is the following:

1. We create an array of the left and right edges of each rectangle, tracking the type of edge (left vs right), it's position and the rectangle it refers to – $\O(n)$ time
2. We sort the array, ordering left edges before right edges – $\O(n \lg n)$ time
3. We create an empty interval tree
4. We iterate the array – $\O(n)$ time
1. If we encounter a left edge, we construct an interval [rect.top, rect.bottom]. We search of it in the interval tree ($\O(\lg n)$). If it's present, we can return an overlap. If it's not, we insert it ($\O(\lg n)$) and continue
2. If we encounter a right edge, we remove the rectangle from the interval tree
5. If we successfully iterate the array without breaking out, we return no overlap

### Python code

from enum import Enum
from collections import deque

def overlap(rectangles):
tree = IntervalTree()
edges = []
intervals = {}

for rectangle in rectangles:
edges.append({'side': 'left', 'key': rectangle.left, 'rect': rectangle})
edges.append({'side': 'right', 'key': rectangle.right, 'rect': rectangle})

edges.sort(key=lambda r: (r['key'], 0 if r['side'] == 'left' else 1))

for edge in edges:
if edge['side'] == 'left':
interval = Interval(edge['rect'].top, edge['rect'].bottom)

if tree.search(interval):
return True

intervals[edge['rect']] = interval
tree.insert(interval)
else:
assert edge['side'] == 'right'
tree.delete(intervals[edge['rect']])

return False

class Rectangle:
def __init__(self, top, bottom, left, right):
assert(top < bottom)
assert(left < right)

self.top = top
self.bottom = bottom
self.left = left
self.right = right

def overlaps(self, other):
return self.top <= other.bottom and other.top <= self.bottom and \
self.left <= other.right and other.left <= self.right

def __repr__(self):
return f"Rectangle(left={self.left}, right={self.right}, top={self.top}, bottom={self.bottom})"

class Interval:
def __init__(self, low, high):
assert low <= high
self.low = low
self.high = high

def __eq__(self, other):
return isinstance(other, Interval) and self.low == other.low and \
self.high == other.high

def __contains__(self, n):
return self.low <= n <= self.high

def __repr__(self):
return f"Interval({self.low}, {self.high})"

__str__ = __repr__

def overlaps(self, other):
return self.low <= other.high and other.low <= self.high

class Color(Enum):
RED = 1
BLACK = 2

NIL_KEY = object()

def other(direction):
if direction == 'left':
return 'right'
elif direction == 'right':
return 'left'
else:
assert(False)

def max_maybe(*args):
return max([arg for arg in args if arg is not None])

class Node:
def __init__(self, color, interval, parent, left, right, max, tree):
self.color = color
self.interval = interval
self.parent = parent
self.left = left
self.right = right
self.tree = tree
self.max = max

def sexp(self):
if self.isNil():
return 'NIL'

color = 'R' if self.color == Color.RED else 'B'

return f"{color}({self.interval}, max={self.max}, {self.left}, {self.right})"

__str__ = sexp

def black_height(self):
node = self
height = 0

while node is not nil:
if node.color == Color.BLACK:
height += 1
node = node.parent

return height

def isRed(self):
return self.color == Color.RED

def isBlack(self):
return self.color == Color.BLACK

def isNil(self):
return self.interval is NIL_KEY

def isNotNil(self):
return not self.isNil()

def __bool__(self):
return self.isNotNil()

def child(self, direction):
if direction == 'left':
return self.left
elif direction == 'right':
return self.right
else:
assert(False)

def set_child(self, direction, child):
if direction == 'left':
self.left = child
elif direction == 'right':
self.right = child
else:
assert(False)

__getitem__ = child
__setitem__ = set_child

def other(self, direction):
return self.child(other(direction))

def rotate(self, direction):
child = self.other(direction)
self[other(direction)] = child[direction]

if child[direction]:
child[direction].parent = self

child.parent = self.parent

if not self.parent:
self.tree.root = child
elif self is self.parent[direction]:
self.parent[direction] = child
else:
self.parent[other(direction)] = child

child[direction] = self
self.parent = child

self.max = max_maybe(
self.interval.high,
self.left.max if self.left else None,
self.right.max if self.right else None,
)

child.max = max_maybe(
child.interval.high,
child.left.max if child.left else None,
child.right.max if child.right else None,
)

def left_rotate(self):
self.rotate('left')

def right_rotate(self):
self.rotate('right')

def transplant(self, other):
if not self.parent:
self.tree.root = other
elif self is self.parent.left:
self.parent.left = other
else:
self.parent.right = other
other.parent = self.parent

def set(self, parent=None, left=None, right=None, color=None):
if color:
self.color = color
if left is not None:
self.left = left
if right is not None:
self.right = right
if parent is not None:
self.parent = parent

def minimum(self):
node = self

while node.left:
node = node.left

return node

nil = Node(Color.BLACK, NIL_KEY, None, None, None, None, None)
nil.parent = nil
nil.left = nil
nil.right = nil

class IntervalTree:
def __init__(self):
self.root = nil

def __str__(self):
return self.root.sexp()

def find(self, interval):
node = self.root

while node:
if node.interval == interval:
return node
elif interval.low < node.interval.low:
node = node.left
else:
node = node.right

return None

def search(self, interval):
node = self.root

while node:
if interval.overlaps(node.interval):
return node
elif node.left and node.left.max >= interval.low:
node = node.left
else:
node = node.right

return None

def nodes(self):
items = deque()

if self.root:
items.append(self.root)

while items:
node = items.popleft()

yield node

if node.left:
items.append(node.left)

if node.right:
items.append(node.right)

def insert(self, interval):
new = Node(Color.RED, interval, None, None, None, interval.high, self)
parent = nil
node = self.root
while node:
parent = node
if new.interval.low < node.interval.low:
node = node.left
else:
node = node.right

new.parent = parent

if not parent:
self.root = new
elif new.interval.low < parent.interval.low:
parent.left = new
else:
parent.right = new

new.set(left=nil, right=nil, color=Color.RED)

self.max_fixup(parent)

self.insert_fixup(new)

def max_fixup(self, node):
while node:
node.max = max_maybe(
node.interval.high,
node.left.max if node.left else None,
node.right.max if node.right else None
)

node = node.parent

def insert_fixup(self, node):
while node.parent.isRed():
if node.parent is node.parent.parent.left:
direction = 'left'
else:
direction = 'right'

if direction == 'left' or direction == 'right':
uncle = node.parent.parent[other(direction)]
if uncle.isRed():
node.parent.color = Color.BLACK
uncle.color = Color.BLACK
node.parent.parent.color = Color.RED
node = node.parent.parent
else:
if node is node.parent[other(direction)]:
node = node.parent
node.rotate(direction)
node.parent.color = Color.BLACK
node.parent.parent.color = Color.RED
node.parent.parent.rotate(other(direction))

self.root.color = Color.BLACK

def delete(self, interval):
deleted = self.find(interval)
y = deleted
y_original_color = y.color

if not deleted.left:
extra_black = deleted.right
deleted.transplant(deleted.right)
self.max_fixup(deleted)
elif not deleted.right:
extra_black = deleted.left
deleted.transplant(deleted.left)
self.max_fixup(deleted)
else:
y = deleted.right.minimum()
y_original_color = y.color
extra_black = y.right

todo = y

if y.parent is deleted:
extra_black.parent = y
else:
todo = y.parent
y.transplant(y.right)
y.right = deleted.right
y.right.parent = y

deleted.transplant(y)
y.left = deleted.left
y.left.parent = y
y.color = deleted.color

self.max_fixup(todo)

if y_original_color == Color.BLACK:
self.delete_fixup(extra_black)

def delete_fixup(self, node):
while node is not self.root and node.isBlack():
if node is node.parent.left:
direction = 'left'
else:
direction = 'right'

sibling = node.parent[other(direction)]

if sibling.isRed():
sibling.color = Color.BLACK
node.parent.color = Color.RED
node.parent.rotate(direction)
sibling = node.parent[other(direction)]

if sibling.left.isBlack() and sibling.right.isBlack():
sibling.color = Color.RED
node = node.parent
else:
if sibling[other(direction)].isBlack():
sibling[direction].color = Color.BLACK
sibling.color = Color.RED
sibling.rotate(other(direction))
sibling = node.parent[other(direction)]

sibling.color = node.parent.color
node.parent.color = Color.BLACK
sibling[other(direction)].color = Color.BLACK
sibling.parent.rotate(direction)
node = self.root

node.color = Color.BLACK