My outputs are:
My algorithm for OFBEAT is O(n^2). It is most probably possible to implement the same ideas in O(n log n) using some kind of tree data structures.
I calculate the number of guarded vertical streets first, then rotate the polygon and do it again.
First I split the polygon into rectangles (sets of vertical streets). Each rectangle ends at the top and at the bottom with a wall. There can also be 0-width rectangles (for vertical streets touching walls to the left and to the right). To compute these rectangles, I scan left-to-right and keep a O(n) size array - for each segment between two different y's I store the number of the current rectangle.
Also, for each rectangle I store a list of rectangles it touches to the left and to the right, along with the segment along which they touch.
This way, I have a graph of rectangles. This graph is in fact a tree. There are O(n) rectangles.
Now for each rectangle I will choose whether or not to guard a vertical street in that rectangle. I will make that decision bottom-up in the tree (starting from the leaves) greedily. Each rectangle (recursively) returns an array of horizontal streets that are covered.
If some horizontal street in a given rectangle is not covered by the children AND it cannot be covered by the parent (because they do not share that street), then we must guard one vertical street in the rectangle. Otherwise, we do not guard any street - we can always postpone it to the parent.