line sweep in 2 dimension

line_sweep_x2.py

#!/usr/bin/env python3

"""
Each point is represented by [x, y], x and y both are floating points.
unit square: with edges either horizontal or vertical, side length 1

Input: n points Output: max number of points can be covered by a unit square

Example:
    input:[[0.1,0.2], [0.5, 0.6], [100, 200], [0.9,0.8]]
    Output: 3
"""

from itertools import accumulate, chain
from typing import List


# some reference https://www.niser.ac.in/~aritra/PlaneSweepAlgorithm.pdf
def line_sweep(xs: List[int]) -> int:
    # basic line sweep algorithm
    # event +1 at original x
    # event -1 at x + 1.0
    ys = sorted(chain.from_iterable([[(x, 1), (x + 1.0, -1)] for x in xs]))
    return max(accumulate(y[1] for y in ys))


def main():
    points = [
        (0.1, 0.2),
        (0.5, 0.6),
        (0.9, 0.8),
        (100, 200),
    ]

    events = sorted(
        chain.from_iterable((((p[0], p), 1), ((p[0] + 1, p), -1)) for p in points)
    )
    mx = 0
    inflights = set()
    # apply line sweep algorithm on xs.
    for (x, p), delta in events:
        print(((x, p), delta))
        if delta == 1:
            inflights.add(p)
            # then apply the line sweep algorith again on ys in range.
            mx = max(mx, line_sweep([p[1] for p in inflights]))
        else:
            inflights.remove(p)

    print(mx)


if __name__ == "__main__":
    main()

https://bubchi89v2.wordpress.com/2014/01/05/interval-tree-point-of-maximum-overlap/
the original problem statement in Introduction to Algorithm 4th edition

17-1 Point of maximum overlap
You wish to keep track of a point of maximum overlap in a set of intervals4a point with the largest number of intervals in the set that overlap it.
a. Show that there is always a point of maximum overlap that is an endpoint of one of the intervals.
b. Design a data structure that efûciently supports the operations INTERVAL- INSERT, INTERVAL-DELETE, and FIND-POM, which returns a point of max- imum overlap. (Hint: Keep a red-black tree of all the endpoints. Associate a value of with each left endpoint, and associate a value of with each right endpoint. Augment each node of the tree with some extra information to maintain the point of maximum overlap.)