tag:blogger.com,1999:blog-264226589944705290.post2915814953190604055..comments2022-11-19T01:08:31.131-08:00Comments on God Plays Dice: The geometry of a gameMichael Lugohttp://www.blogger.com/profile/15671307315028242949noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-264226589944705290.post-85368290817570469192008-11-18T11:23:00.000-08:002008-11-18T11:23:00.000-08:00To clarify suresh's idea:Take a point in the top r...To clarify suresh's idea:<BR/><BR/>Take a point in the top row. Now what you have left is a U-shaped path of potential spots.<BR/><BR/>Now choose the topmost point on the left branch, or if it's empty take the leftmost point on the bottom, or if that's empty take the bottommost point on the right.<BR/><BR/>Now worst case you have a line segment; take one endpoint of that line segment, and you're done.<BR/><BR/>The last bit is a little handwavy but I think it's easy enough to fill in the details. The key is that the U isn't square but has a bottom that's at least twice as wide as the verticals. So when you choose the point on the U, it's not equidistant from points on two sides, and once you measure that distance you get points on just one side of the U.Joshua Zuckerhttps://www.blogger.com/profile/04689961247338617418noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-72296432113778210062008-11-16T06:38:00.000-08:002008-11-16T06:38:00.000-08:00More to the point, let's examine exactly what was ...More to the point, let's examine exactly what was said:<BR/><BR/><I>pick a shell that's on the orthogonal hull (i.e nothing to left or above it)</I><BR/><BR/>But now let's assume the upper-left corner is unoccupied, but there are shells in both the left column and top row. Now the way you're saying to pick the point <I>might leave something to the left of it</I>, against your conditions from before.<BR/><BR/>I'm not saying you're wrong in the general idea, but you have to be more careful in how you specify things.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-77892708816567306932008-11-16T01:15:00.000-08:002008-11-16T01:15:00.000-08:00Suresh: choosing that point may induce more than t...Suresh: choosing that point may induce more than two lines.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-10973430031950216742008-11-15T00:34:00.000-08:002008-11-15T00:34:00.000-08:00unapologetic: not sure what you mean. to be more p...unapologetic: not sure what you mean. to be more precise: <BR/><BR/>take the top most occupied row of the grid. In that row, take the left most point.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-32909111544333104502008-11-14T07:45:00.000-08:002008-11-14T07:45:00.000-08:00suresh: I can easily draw examples that have no su...suresh: I can easily draw examples that have no such point as the one you suggest starting with.<BR/><BR/>marty: in the l^\infty norm there can be many points of intersection of two circles. Be careful!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-90001028279472756612008-11-14T07:15:00.000-08:002008-11-14T07:15:00.000-08:00Finding the pearl is akin to drawing geometric cir...Finding the pearl is akin to drawing geometric circles. Pick a shell, and (assuming you didn't find the pearl) draw a circle of the given distance centered on that shell. <BR/><BR/>Pick any shell on that circle. If it's not a match, you draw a second circle with the new distance. <BR/><BR/>Now you have two circles, with two points of intersection. The pearl is in one or the other, so you need no more than four shells opened.Martyhttps://www.blogger.com/profile/16416366317000047727noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-10283130991930878162008-11-14T01:09:00.000-08:002008-11-14T01:09:00.000-08:00Problem 1: pick a shell that's on the orthogonal h...Problem 1: pick a shell that's on the orthogonal hull (i.e nothing to left or above it). The answer induces two orthogonal lines where the pearl can lie. <BR/><BR/>If we know which of the two lines we are on, it takes at most two clicks. Pick an extreme point, and the offset uniquely defines the location.<BR/><BR/>However, finding this line takes one click (pick a point furthest from the intersection of the two lines). <BR/><BR/>Total: 1 + 1 + 2 = 4. <BR/><BR/>For higher dimensional variants: the first click defines d (d-1)-facets. Selecting which one to recurse on takes d-1 clicks (extreme points in each facet). This defines the recurrence<BR/><BR/>T(d) = 1 + d-1 + T(d-1)<BR/>T(1) = 2<BR/><BR/>T(d) is d(d+1)/2 + 1. <BR/><BR/>This could probably be optimized slightly, by also querying the corner opposite the first query, but the asymptotics would remain the same, I think. <BR/><BR/>I'd hazard that a similar result holds for L_1, but I'm not terribly sure.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.com