Efficient optimal overlap removal: algorithms and experiments

W. Meulemans (Corresponding author)

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

10 Citaten (Scopus)
285 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.

Originele taal-2Engels
Pagina's (van-tot)713-723
Aantal pagina's11
TijdschriftComputer Graphics Forum
Nummer van het tijdschrift3
StatusGepubliceerd - 10 jul. 2019


Duik in de onderzoeksthema's van 'Efficient optimal overlap removal: algorithms and experiments'. Samen vormen ze een unieke vingerafdruk.

Citeer dit