Largest area convex hull of imprecise data based on axis-aligned squares

In recent years, more and more algorithms related to imprecise data have been proposed. Specifically, some algorithms on computing the maximum area convex hull are designed recently when the imprecise data are modeled as non-overlapping axis-aligned squares or as equal size squares. The time complexity of the best known algorithm based on non-overlapping axis-aligned squares is O(n7). If the squares have equal size and can overlap, the time complexity of the best known algorithm is O(n5). In this paper, we improve the former from O(n7) to O(n5) and improve the latter from O(n5) to O(n2). These results are obtained by exploiting the non-trivial geometric properties of the problems.