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:

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
We sort the array, ordering left edges before right edges – $\O(n \lg n)$ time
We create an empty interval tree
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
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