tag:blogger.com,1999:blog-593563533834706486.post8228859344615122414..comments2024-03-20T19:41:44.472-04:00Comments on Yet Another Math Programming Consultant: Looks difficult to meErwin Kalvelagenhttp://www.blogger.com/profile/09496091402502236997noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-593563533834706486.post-19180120883984242152010-03-22T13:27:28.590-04:002010-03-22T13:27:28.590-04:00Some references are in http://en.wikipedia.org/wik...Some references are in <a href="http://en.wikipedia.org/wiki/Largest_empty_rectangle" rel="nofollow">http://en.wikipedia.org/wiki/Largest_empty_rectangle</a>.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-3247596246757449362010-03-21T21:28:57.429-04:002010-03-21T21:28:57.429-04:00Do the sides of the rectangle have to be parallel ...Do the sides of the rectangle have to be parallel with the sides of the unit square? If not this problem is really hard.<br /><br />Otherwise I'd go for a largest circle first, then find a large box.pihttps://www.blogger.com/profile/00954503509976411806noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-8790348942181496982010-03-21T21:09:07.835-04:002010-03-21T21:09:07.835-04:00The main disadvantage I see with genetic programmi...The main disadvantage I see with genetic programming is that it is often not clear how good the solutions are. It finds better and better solutions, but how far we are from a global optimum is often just a guess. But it is well known that for some difficult problems it can do extremely well.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-33551451091725289322010-03-21T19:27:06.473-04:002010-03-21T19:27:06.473-04:00Hmm, on further review, please disregard my commen...Hmm, on further review, please disregard my comment. ;)Peternoreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-84025109096093842642010-03-21T19:00:12.129-04:002010-03-21T19:00:12.129-04:00I have actually once solved a similar problem (sam...I have actually once solved a similar problem (same but with largest circle) with genetic programing. it works very well.Anonymoushttps://www.blogger.com/profile/06647309638775171957noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-84433946372271022892010-03-21T18:42:10.852-04:002010-03-21T18:42:10.852-04:00Well, I would agree that it isn't easy if you ...Well, I would agree that it isn't easy if you are starting from scratch, but this sort of task is fairly straightforward with standard image processing packages.<br /><br />Say you have a binary image with your n points as black pixels on a white background. Modify that image by going through each point and blacking out the entire row and entire column of each point. You now have an image with a bunch of lines. These black lines outline a bunch of white rectangles, which are your candidate rectangles.<br /><br />Now you can run a standard blob-finding routine to get a list of the rectangles, which you can easily sort by area or apply constraints as you wish. <br /><br />I know Intel IPP and Matlab have blob-finding built into their image processing toolboxes. I am not familiar with R . . . you may need to implement your own blob finding routine . . . one place you might look for help is openCV's open source implementation (C++). http://opencv.willowgarage.com/wiki/cvBlobsLib#AlgorithmPeterhttp://peterkenji.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-35609070847683892572010-03-21T18:40:25.548-04:002010-03-21T18:40:25.548-04:00I guess the solution rectangle has to be aligned w...I guess the solution rectangle has to be aligned with the unit square?<br /><br />This problem reminds me of this one paper of applied topology: "Homological Sensor" networks. In that paper, the dropped sensors on some area. The sensors had a given range, thus defining a neighborhood graph. From this graph, you can construct a higher-dimensional simplicial complex and compute its homology groups. This way, they could detect holes in the area, not covered by points.<br /><br />You could interprete your points as sensors and play a little with the range. Of course, the holes found by this method are purely topological, independent of size and shape. It might still be fun to try.<br /><br />Link to paper:<br />http://www.math.uiuc.edu/~ghrist/preprints/noticesdraft.pdf<br /><br />There is already some software available, to compute the homology:<br />http://chomp.rutgers.edu/<br /><br />In any case, you can learn some new trick :-)Robert Schwarzhttp://rschwarz.netnoreply@blogger.com