Demonstrating polynomial run-time growth for local search matching

Abstract

Local search is a well established and highly effective general method for solving complex combinatorial optimization problems. We've developed local search techniques to solve difficult geometric matching problems. Matching is posed as the problem of finding the optimal many-to-many correspondence mapping between a line segment model and image line segments. Image data is assumed to be fragmented, noisy and cluttered. These algorithms have been used for robot navigation, photo-interpretation and scene understanding. This paper explores how local search performs as model complexity increases, image clutter increases, and additional model instances are added to the image data. Expected run-times to find optimal matches with 95% confidence are determined for 48 distinct problems involving 6 models. Non-linear regression is used to estimate run-time growth as a function of problem size. Both polynomial and exponential growth models are fit to the run-time data. For problems with random clutter the polynomial model fits better and growth is comparable to that for tree search. For problems involving symmetric models and multiple model instances, where tree search is exponential, growth rates for local search remain closer to polynomial than exponential.