After seeing this paper on arXiv, Timothy Chan pointed out to us that
a very similar (almost identical) data structure appears in Section 4.4
of the paper

P. Afshani, J. Barbay, and T. M. Chan
Instance-optimal geometric algorithms
in Proceedings of FOCS 2009.
http://www.cs.uwaterloo.ca/~tmchan/abc_4_09.ps

Many of the problems considered in Section 5 of our paper are also
covered in Section 4 of the above paper.