Timeline for Voronoi diagram in a graph
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 11, 2011 at 5:55 | comment | added | Sariel Har-Peled | So now I am thinking maybe there is an interesting question here. What if the underlying metric is a manifold (as suggested by Suresh). Now, we connect two points if and only if there exists a third point q, such the other two points are the two nearest neighbors (think about this as some kind of witness complex). A natural conjecture would be that if the manifold is doubling, then one can always add O(1) points such that the bisector is connected. Hmmm... | |
| Dec 10, 2011 at 8:22 | history | tweeted | twitter.com/#!/StackCSTheory/status/145417988667998208 | ||
| Dec 9, 2011 at 20:47 | comment | added | Josephine Moeller | For Q1, a simpler counterexample is the bisector of $S$ where $S$ is the left side of $K_{2, n}$. The bisector is totally disconnected. | |
| Dec 9, 2011 at 0:21 | comment | added | Joseph O'Rourke | @Suresh: Yes, I see now, sorry for not catching your point immediately! | |
| Dec 8, 2011 at 23:07 | comment | added | Suresh Venkat | ah so on the regular sphere a voronoi cell can't get bigger than a hemisphere, so you don't have this problem. But my comment more generally was the same as Sariel's in that you're asking for convexity of voronoi cells in a potentially generic riemannian manifold and that's shouldn't be true. | |
| Dec 8, 2011 at 21:50 | comment | added | Joseph O'Rourke | Thanks, Sariel, for those observations. Yes, it appears I was hoping for too much, and perhaps only in special classes of graphs will there be nice structural properties. | |
| Dec 8, 2011 at 20:09 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 9 characters in body
|
| Dec 8, 2011 at 20:09 | comment | added | Sariel Har-Peled | For Q1 to make sense you need some sense of faces, right? Otherwise, the "real" bisector is in the middle of edges, and introducing vertices just before and after this point, guarantees that the bisector is disconnected. Maybe if you assume the graph is chordal you can prove something. As for Q2: this is false even for geodesics in a polygon with holes (or terrains). My guess would be that you need to assume something quite strong on the graph to get non-trivial answer to both questions. | |
| Dec 8, 2011 at 19:52 | comment | added | Joseph O'Rourke | @Suresh: Could you expand your remark to indicate how one achieves nonconvexity on the sphere? | |
| Dec 8, 2011 at 19:51 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 188 characters in body
|
| Dec 8, 2011 at 18:22 | comment | added | Suresh Venkat | Regarding Q2: Surely this should be no in general, because it's not true for Riemannian manifolds in general (cf the sphere). Might be interesting to ask what the discrete equivalent of the injectivity radius. | |
| Dec 8, 2011 at 16:25 | answer | added | David Eppstein | timeline score: 8 | |
| Dec 8, 2011 at 16:14 | history | asked | Joseph O'Rourke | CC BY-SA 3.0 |