Re: Fit rectangle to set of points

*To*: mathgroup at smc.vnet.net*Subject*: [mg69349] Re: Fit rectangle to set of points*From*: "David W.Cantrell" <DWCantrell at sigmaxi.net>*Date*: Thu, 7 Sep 2006 23:58:45 -0400 (EDT)*References*: <edom0n$hu2$1@smc.vnet.net>

"buttgereit at biomediclab.de" <buttgereit at biomediclab.de> wrote: > Dear Group, > > I have a set of 2D points given for which I would like to find the > smallest rectangle circumscribing all the points. Smallest perimeter or smallest area or ...? I will assume you want smallest area. > Doing this with a circle instead of a rectangle was easy --- for the > rectangle I don't see the trick. > > Any hints? Of course you need consider only the convex hull of your set of points. A function for finding the convex hull is in the standard package DiscreteMath`ComputationalGeometry` . Have you looked at the literature on this topic? A Google web search for "smallest enclosing rectangle" led me to, among other references, <http://ceng.usc.edu/~prasanna/papers/jang-97.pdf>. Please see their section 3.2 . David