Hans W Borchers <hwborchers <at> googlemail.com> writes: > > For an application in image processing -- using R for statistical purposes -- I > need to solve the following task: > > Given n (e.g. n = 100 or 200) points in the unit square, more or less randomly > distributed. Find a rectangle of maximal area within the square that does not > contain any of these points in its interior. > > If a, b are height and width of the rectangel, other constraints may have to be > imposed such as a, b <= 0.5 and/or 0.5 <= a/b <= 2.0 . The rectangle is > allowed to touch the border of the square. > > For each new image the points will be identified by the application, like all > stars of a certain brightness on an astronomical picture. So the task will have > to be performed several times. > > I assume this problem is computationally hard. I would like to find a solution > that is reasonably fast for n = 100..200 points. Exhaustive search along the > x, y coordinates of the points will not be fast enough. > > I know this request is not about R syntax and does not contain 'repro-code'. But > perhaps a somehow similar problem has been solved before. > > Thanks in advance for any suggestions, > Hans Werner >
I solved this with a simple minded MINLP formulation using BARON (a global solver). This seems to produce solutions relatively quickly (somewhat slower for n=200). Actually this solved easier than I expected. See: http://yetanothermathprogrammingconsultant.blogspot.com/2010/03/looks-difficult- to-me-2.html ---------------------------------------------------------------- Erwin Kalvelagen Amsterdam Optimization Modeling Group er...@amsterdamoptimization.com http://amsterdamoptimization.com ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
