Jump to content

Talk:Bounding sphere

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

"Bouncing Bubble" looks very much like [Wikipedia:SELFPUB] (nor does the animation look like it's O(n)). My apologies if I'm mistaken, but this doesn't feel right to me. I'm writing an expanded section on Welzl's Algorithm since it's a) simple b) a good fit for what I'm doing and c) not self-published. 50.157.249.13 (talk) 21:52, 10 June 2013 (UTC)[reply]

[edit]

Hello fellow Wikipedians,

I have just modified one external link on Bounding sphere. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 16:24, 6 November 2016 (UTC)[reply]

Ritter's algorithm misunderstood

[edit]

I found the description on Ritter's algorithm here a bit confusing, so I did a little search and found this:

https://www.researchgate.net/publication/242453691_An_Efficient_Bounding_Sphere

It'd seem to me, that the principle has not been understood very well: According to the paper the first run selects three pairs of points that represent the maximum and minimum coordinates in three directions. Obviously some of the points may be the same ones, though that is not pointed out in the paper. Then the pair, that has the greatest distance between them, is selected to form the initial candidate for the sphere. On the second run the sphere is expanded every time, that a point outside the sphere is found. In the process both the radius and the center point get updated in the same step.

Peteihis (talk) 15:30, 1 April 2019 (UTC)[reply]

I totally agree, and I could not find a single source describing steps 1 and 2 as they are in this article. I implemented it the way Ritter described it and it works much better. I easily improved it by looking for the extrema along the diagonals, as well as along the axes as described in the original article, and obtained even better results.

Steps 1 and 2 should be replaced by step 1 from Ritter's paper:

Make one (quick) pass through the N points. Find these six points: - The point with minimum x, the point with maximum x, - The point with minimum y, the point with maximum y, - The point with minimum z, the point with maximum z. This gives three pairs of points. Each pair has the maximum span for its dimension. Pick the pair with the maximum point-to-point separation (which could be greater than the maximum dimensional span). Calculate the initial sphere, using this pair of points as a diameter.

And it can be improved by adding these four pairs of points: - The point with minimum x+y+z, the point with maximum x+y+z, - The point with minimum x+y-z, the point with maximum x+y-z, - The point with minimum x-y+z, the point with maximum x-y+z, - The point with minimum x-y-z, the point with maximum x-y-z. Fredyd (talk) 02:25, 15 June 2019 (UTC)[reply]