Efficient Optimal Overlap Removal: Algorithms and Experiments

Abstract

Motivated by visualizing spatial data using proportional symbols, we study the following problem: given a set of overlapping squares of varying sizes, minimally displace the squares as to remove the overlap while maintaining the orthogonal order on their centers. Though this problem is NP-hard, we show that rotating the squares by 45 degrees into diamonds allows for a linear or convex quadratic program. It is thus efficiently solvable even for relatively large instances. This positive result and the flexibility offered by constraint programming allow us to study various trade-offs for overlap removal. Specifically, we model and evaluate through computational experiments the relations between displacement, scale and order constraints for static data, and between displacement and temporal coherence for time-varying data. Finally, we also explore the generalization of our methodology to other shapes.