tag:blogger.com,1999:blog-6555947.post113869169877848158..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: STOC 2006 results outSuresh Venkatasubramaniannoreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6555947.post-1138897345667335982006-02-02T09:22:00.000-07:002006-02-02T09:22:00.000-07:00There's also "The distance trisector curve " ...There's also "<A HREF="http://kam.mff.cuni.cz/~matousek/trisec.ps.gz" REL="nofollow">The distance trisector curve</A> " by Asano, Matousek, and Tokuyama, which gets my vote for the "Least Likely Geometry Paper To Be Submitted, Never Mind Accepted, To STOC" award. It's a very cool paper, but still....Jeff Ericksonhttp://www.blogger.com/profile/08256919779078679044noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1138763665944714322006-01-31T20:14:00.000-07:002006-01-31T20:14:00.000-07:00There are two MWT papers. This is a (1+epsilon) ap...There are two MWT papers. This is a (1+epsilon) approximation; the other one (not submitted to STOC) is the NP-completeness proof.D. Eppsteinhttp://11011110.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1138762810047631372006-01-31T20:00:00.000-07:002006-01-31T20:00:00.000-07:00Ahhh. I was looking for the MWT paper. I had heard...Ahhh. I was looking for the MWT paper. I had heard something about it. Thanks for the pointers.  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SureshSureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1138759156298418042006-01-31T18:59:00.000-07:002006-01-31T18:59:00.000-07:00I would add to the list:- Searching Dynamic Point ...I would add to the list:<BR/>- Searching Dynamic Point Sets in Spaces with Bounded Doubling Dimension.<BR/>Richard Cole and Lee-Ad Gottlieb <BR/>They show how to maintain ANN dynamically in low doubling dimension spaces. Not a simple result, but still nice.<BR/><BR/>- A Quasi-Polynomial Time Approximation Scheme for Minimum Weight Triangulation,<BR/>Jan Remy and Angelika Steger. <BR/>If this is what the title claims, that this is an interesting result, especially considering the SoCG submission showing the problem is npc.<BR/><BR/><BR/><BR/>Somewhat surprisingly, Vladlen result did not get in. Overall a lot of geometry papers for STOC.<BR/><BR/><BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SarielAnonymousnoreply@blogger.com