Fast Node Overlap Removal — Addendum
Tim Dwyer, Kim Marriott, Peter J. Stuckey · 2006
Abstract. This document highlights an oversight in our recent paper on a method for node overlap removal [1, 2]. The error, based on an incompleted specified invariant, occurs in the algorithm satisfy VPSC and leads to a rarely occurring case where not all constraints are satisfied. We give the required additions to the algorithm to obtain correct behaviour, revise the worst case complexity theorem and reproduce the experimental performance data. While the worst case complexity is O(n 2) we show that for typical input the performance is O(n log n) and this is reflected by the new experimental results.