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.