Efficient optimal overlap removal: algorithms and experiments

W. Meulemans (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)
279 Downloads (Pure)


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.

Original languageEnglish
Pages (from-to)713-723
Number of pages11
JournalComputer Graphics Forum
Issue number3
Publication statusPublished - 10 Jul 2019


  • Human-centered computing
  • Visualization


Dive into the research topics of 'Efficient optimal overlap removal: algorithms and experiments'. Together they form a unique fingerprint.

Cite this