Reduction algorithm for the NPMLE for the distribution function of bivariate interval-censored data

This article considers computational aspects of the nonparametric maximum likelihood estimator (NPMLE) for the distribution function of bivariate interval-censored data. The computation of the NPMLE consists of a parameter reduction step and an optimization step. This article focuses on the reduction step and introduces two new reduction algorithms: the Tree algorithm and the HeightMap algorithm. The Tree algorithm is mentioned only briefly. The HeightMap algorithm is discussed in detail and also given in pseudo code. It is a fast and simple algorithm of time complexity O(n(2)). This is an order faster than the best known algorithm thus far by Bogaerts and Lesaffre. We compare the new algorithms to earlier algorithms in a simulation study, and demonstrate that the new algorithms are significantly faster. Finally, we discuss how the HeightMap algorithm can be generalized to d-dimensional data with d > 2. Such a multivariate version of the HeightMap algorithm has time complexity O(n(d)).