# Exercise 14.1.8

$\star$ Consider $n$ chords on a circle, each defined by its endpoints. Describe an $\O(n \lg n)$-time algorithm to determine the number of pairs of chords that intersect inside the circle. (For example, if the $n$ chords are all diameters that meet at the center, then the correct answer is $\binom n 2$.) Assume that no two chords share an endpoint.

It's an interesting algorithm:

def count_chords(chords):
points = []

for (start, end) in chords:
if start > end:
start, end = end, start

points.append({'kind': 'start', 'x': start})
points.append({'kind': 'end', 'x': end, 'start': start})

points = sorted(points, key=lambda point: point['x'])

tree = Tree()
count = 0

for point in points:
if point['kind'] == 'start':
tree.insert(point['x'])
else:
assert point['kind'] == 'end'

count += tree.size() - tree.search(point['start']).rank()
tree.delete(point['start'])

return count


First, we sort all the points, all while keeping track of whether they are the start or the end of an interval, and how to look up the start from the end point. This takes $\O(n \lg n)$ time because of the sort. We can now iterate the points in order.

Next, we need to consider the following invariant:

If $a$ and $b$ are the start and end of a chord, then it intersects with all chords that have start $s$ such that $a < s < b$ and end $e$ such that $e > b$.

That is, every chord that starts between the two endpoints of another will intersect with it, if it's endpoint is outside this range. Note that this holds true in the other direction as well ($s < a < e < b$), but this will double-count the intersection. Thus, we interested only in counting pairs $(a, b)$ and $(s, e)$, such that $a < s < b < e$.

The way we can do that is by iterating over the points and doing the following:

• If we encounter a start point, we insert it into the tree ($\O(\lg n)$)
• If we encounter an end point, we look up the rank of the start point ($\O(\lg n)$) and use it to determine how many chords start after it, but have not ended yet, and add it up. Then we remove the start point from the tree ($\O(\lg n)$).

Each step is at most an $\O(\lg n)$ operation, and since we perform $2n$ of them, the total time is $\O(n \lg n)$.

### Python code

from enum import Enum
from collections import deque

def count_chords(chords):
points = []

for (start, end) in chords:
if start > end:
start, end = end, start

points.append({'kind': 'start', 'x': start})
points.append({'kind': 'end', 'x': end, 'start': start})

points = sorted(points, key=lambda point: point['x'])

tree = Tree()
count = 0

for point in points:
if point['kind'] == 'start':
tree.insert(point['x'])
else:
assert point['kind'] == 'end'

count += tree.size() - tree.search(point['start']).rank()
tree.delete(point['start'])

return count

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)

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

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

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

return f"{color}({self.key}, {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.key 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

child.size = self.size
self.size = self.left.size + self.right.size + 1

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

def select(self, i):
node = self

while node:
rank = node.left.size + 1
if i == rank:
return node
elif i < rank:
node = node.left
else:
i -= rank
node = node.right

assert(False)

def rank(self):
rank = self.left.size + 1

node = self

while node.parent:
if node == node.parent.right:
rank += node.parent.left.size + 1
node = node.parent

return rank

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

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

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

def size(self):
return self.root.size

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

while node:
if node.key == key:
return node
elif key < node.key:
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 select(self, i):
return self.root.select(i)

def insert(self, key):
new = Node(Color.RED, key, None, None, None, self, 1)
parent = nil
node = self.root
while node:
node.size += 1

parent = node
if new.key < node.key:
node = node.left
else:
node = node.right

new.parent = parent

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

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

self.insert_fixup(new)

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, key):
def decrease_ancestor_sizes(node):
while node:
node.size -= 1
node = node.parent

deleted = self.search(key)
y = deleted
y_original_color = y.color

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

decrease_ancestor_sizes(y)

if y.parent is deleted:
extra_black.parent = y
else:
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
y.size = y.left.size + y.right.size + 1

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