tag:blogger.com,1999:blog-6042417775578107106.post2797691278241312591..comments2023-08-05T11:30:32.754-04:00Comments on The Hacks of Life: Randomized Bounding SpheresChrishttp://www.blogger.com/profile/14648675681957285299noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-6042417775578107106.post-69717325752188599632011-01-09T01:55:30.724-05:002011-01-09T01:55:30.724-05:00tixxit - the algo in that paper _is_ X-Plane's...tixxit - the algo in that paper _is_ X-Plane's "cheap" (one-pass) sphere algo. I'm not sure if the algo is original to Chan - we developed it internally but never bothered to do rigorous analysis on its quality.<br /><br />(It was the obvious improvement over first-pt-is-center or centroid-is-center.)<br /><br />The random permuted version simply runs that algo multiple times in random order.Benjamin Supnikhttps://www.blogger.com/profile/04886313844644521178noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-56895150329926174862011-01-08T17:15:51.201-05:002011-01-08T17:15:51.201-05:00Check out Timothy Chan's "A simple stream...Check out Timothy Chan's "A simple streaming algorithm for minimum enclosing balls." It is similar to your algorithm, would be just as quick, but it guarantees a 3/2 (radius) approximation to the minimum enclosing ball. The algorithm is dead simple and works fantastically.tixxithttps://www.blogger.com/profile/00895656795952782701noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-18741377012446779332009-10-27T09:24:08.072-04:002009-10-27T09:24:08.072-04:00Megiddo is linear time but - look at the geometric...Megiddo is linear time but - look at the geometric primitives in each step...it's going to be a slow linear time.<br /><br />Welzl is more useful in practice - see here.<br /><br />http://www.gamedev.net/reference/programming/features/welzlminsphere/<br /><br />What I am doing can be thought of as sort of "imperfect in optimization" instead of "imperfect in time".<br /><br />Basically my algorithm skips the expensive restart steps and uses the incorrect (but close) incremental addition prt of Welzl's algorithm, but by running on multiple permutations, I can get luckier about what points define the sphere.Benjamin Supnikhttps://www.blogger.com/profile/04886313844644521178noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-42167073983785881642009-01-30T15:36:00.000-05:002009-01-30T15:36:00.000-05:00@baby-rabbit: Your assumption that the centre of t...@baby-rabbit: Your assumption that the centre of the sphere is the average of the points is wrong. If you tried to prove it you'd quickly find counterexamples...Sumuduhttps://www.blogger.com/profile/01263131492343790978noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-89965049142174579782009-01-29T19:00:00.000-05:002009-01-29T19:00:00.000-05:00The centre of the sphere is the average x/y/z of a...The centre of the sphere is the average x/y/z of all the points, the radius is from the point furthest from this center - thats O(N) and with a bit more maths can be done in a single pass.baby-rabbithttps://www.blogger.com/profile/15049667572937404392noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-67383025690331590572009-01-26T09:02:00.000-05:002009-01-26T09:02:00.000-05:00@jsnx: That would be "Linear-Time Algorithms for L...@jsnx: That would be "Linear-Time Algorithms for Linear Programming in R³ and Related Problems", available at http://theory.stanford.edu/~megiddo/pdf/lp3.pdfUnknownhttps://www.blogger.com/profile/00993135746502696254noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-90779676687925626462009-01-25T08:08:00.000-05:002009-01-25T08:08:00.000-05:00@BioTronic: Which paper is it?@BioTronic: Which paper is it?Jason Dusekhttps://www.blogger.com/profile/15702067426651391511noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-70565241269899183152009-01-24T23:01:00.000-05:002009-01-24T23:01:00.000-05:00@BioTronic: Aha! Thanks for showing me the error o...@BioTronic: Aha! Thanks for showing me the error of my ways.Jason Reidhttps://www.blogger.com/profile/02749906366794684228noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-11157013534925151242009-01-24T22:43:00.000-05:002009-01-24T22:43:00.000-05:00@Jason: Consider the three points (1, 1), (1.1, 0)...@Jason: Consider the three points (1, 1), (1.1, 0), and (0, 1.1). Your algorithm would create a bounding sphere with a radius of 1.1, while it should have been sqrt(2). (simplified, you might need more points for this to be true)<BR/><BR/>On the other hand, Nimrod Megiddo published an algorithm in 1984, which creates a bounding sphere in linear time.Unknownhttps://www.blogger.com/profile/00993135746502696254noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-7366319648200174842009-01-24T21:03:00.000-05:002009-01-24T21:03:00.000-05:00@Jason: That's exactly what I was thinking...@Jason: That's exactly what I was thinking...Unknownhttps://www.blogger.com/profile/08986461981313549364noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-12069093573023723192009-01-24T17:36:00.000-05:002009-01-24T17:36:00.000-05:00Maybe I'm misunderstanding the problem (or sho...Maybe I'm misunderstanding the problem (or showing off my poor algorithms skillz)...but can't you do a linear time scan through the points for Max X, Y, and Z and Min X, Y, and Z, and using those values to calculate a bounding sphere?<BR/><BR/><BR/>for each point {<BR/> if x < min_x: min_x = x<BR/> if y < min_y: min_y = y<BR/> if z < min_z: min_z = z<BR/> if x > max_x: max_x = x<BR/> if y > max_y: max_y = y<BR/> if z > max_z: max_z = z<BR/>}<BR/>dx = max_x - min_x<BR/>dy = max_y - min_y<BR/>dz = max_z = min_z<BR/>center = (min_x + dx/2,<BR/> min_y + dy/2,<BR/> min_z + dz/2<BR/>)<BR/>bounds = sphere(center, max(dx,dy,dz))Jason Reidhttps://www.blogger.com/profile/02749906366794684228noreply@blogger.comtag:blogger.com,1999:blog-6042417775578107106.post-75958151250943014722009-01-24T17:33:00.000-05:002009-01-24T17:33:00.000-05:00This comment has been removed by the author.Jason Reidhttps://www.blogger.com/profile/02749906366794684228noreply@blogger.com