From jsbm@ams.sunysb.edu Sat Jan 29 12:31:55 2005 Return-Path: Received: from sbexim1.cs.sunysb.edu (sbexim1 [130.245.1.151]) by sbcs.cs.sunysb.edu (8.12.3/8.12.3) with ESMTP id j0THVoVh021215; Sat, 29 Jan 2005 12:31:50 -0500 (EST) Received: from sbexim1.cs.sunysb.edu (sbexim1 [130.245.1.151]) by sbexim1.cs.sunysb.edu (8.12.9/8.12.11) with SMTP id j0THVcNM017135; Sat, 29 Jan 2005 12:31:48 -0500 (EST) Received: from sbexim0.cs.sunysb.edu ([130.245.1.149]) by sbexim1.cs.sunysb.edu (NAVGW 2.5.2.12) with SMTP id M2005012912314700063 ; Sat, 29 Jan 2005 12:31:47 -0500 Received: from catbert.ams.sunysb.edu (catbert.ams.sunysb.edu [129.49.108.32]) by sbexim0.cs.sunysb.edu (8.12.10/8.12.10) with ESMTP id j0THVmVC025434; Sat, 29 Jan 2005 12:31:48 -0500 (EST) Received: from joepc.ams.sunysb.edu (joepc [129.49.108.107]) by catbert.ams.sunysb.edu (8.11.7p1+Sun/8.11.6) with ESMTP id j0THW4M27137; Sat, 29 Jan 2005 12:32:04 -0500 (EST) Received: from jsbm by joepc.ams.sunysb.edu with local (Exim 3.36 #1 (Debian)) id 1CuwS8-0003BX-00; Sat, 29 Jan 2005 12:32:08 -0500 Date: Sat, 29 Jan 2005 12:32:08 -0500 To: Yue Wang Cc: skiena@cs.sunysb.edu, bender@cs.sunysb.edu, george@georgehart.com, ghart@optonline.net, alexmohr@joepc.ams.sunysb.edu, Esther Arkin , abasu@cs.sunysb.edu Subject: Re: About today's seminar notes Message-ID: <20050129173208.GA12231@joepc> References: Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="Dxnq1zWXvFF0Q93v" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.3.28i From: Joseph Mitchell Content-Length: 6137 Status: RO --Dxnq1zWXvFF0Q93v Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Hi Yue! Thanks for agreeing to scribe! Indeed, yes, I did jot down some notes of my own about the discussions yesterday. Feel free to use this as a starting point for any of your own notes. Joe On Fri, Jan 28, 2005 at 04:07:29PM -0500, Yue Wang wrote: > hi, Professor, > > Do you have any materials about the problem you said in today's > seminar? If yes, I want to refer to them in order to scribe the notes. > Thanks a lot!:) > > Best wishes, > Yue --Dxnq1zWXvFF0Q93v Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename=notes-1-28-05 \section*{Reading Group, 1/28/05} Joe suggested the following problem: Given a set $S=\{p_1,\ldots,p_n\}$ of $n$ points in the Euclidean plane. For a positive integer $k$, define the graph $NNG_k(S)$ to be the graph whose nodes are the points $S$ and whose edges join each $p_i$ to the $k$ nearest neighbors of $p_i$. The question is, for what values of $k$ is $NNG_k(S)$ a planar graph? Also, for which values of $k$ is the straight-line layout (with edges drawn as straight segments, and with node embedded at points $S$) a ``plane graph'', i.e., an embedding with no crossing edges? This problem arose in a SoCG'05 submission that used a similar graph as a starting point for mesh generation. First, we note that $NNG_1(S)$ is planar; in fact, $NNG_1(S)$ is just the usual ``nearest neighbor graph'' of $S$, and it is planar because it is a subgraph of the Delaunay diagram. Note that we can define $NNG_k(S)$ quite naturally as a {\em directed} graph, with a directed arc leading from $p_i$ to each of its $k$ nearest neighbors. Note too that there is an issue of degeneracy here: what if many points are tied for being nearest (or second-nearest) neighbors of $p_i$? We can resolve the ties in a couple natural ways: (1) pick the $k$ nearest neighbors randomly whenever there are ties; (2) connect $p_i$ to {\em all} neighbors that are closest, then to all neighbors that are second-closest, etc. Another option is to focus on the case of general position points. We examined the question of whether or not $NNG_2(S)$ is planar. Joe showed a simple example with two edges that cross: (0,-1), (1,0), (1.1,0), (2,-1). Here, $NNG_2(S)$ is planar, but its embedding has one pair of crossing edges. Steve pointed out that $NNG_4(S)$ can be trivially nonplanar: just define $S$ to be 5 points in convex position, and $NNG_4(S)$ is $K_5$, the nonplanar complete graph on 5 nodes. We modified this example to show that $NNG_2(S)$ may also be nonplanar, by replacing $S$ with lots of points that lie along (curved) arcs in an embedding of $K_5$, thereby showing that $NNG_2(S)$ contains a ``subdivision'' of $K_5$ (which also must be nonplanar). We had to be careful at two places: (1) at the 5 nodes of the original $K_5$, we want the four sequences of points that approach the node to be well separated (entering with separation at least 60 degrees -- we easily get separation of 90 degrees). (2) at places where the edges of $K_5$ cross, we need the sequence of points along the edges to be such that the edges of the subdivision graph also cross (not ``cross'' at a common vertex). For this, we use Joe's crossing gadget. The final result is this: $NNG_k(S)$ is always planar (and in fact its straight edge embedding is noncrossing) for $k=1$, but it can already by nonplanar for $k=2$ (and therefore also for larger values of $k$). Joe then suggested the definition of another natural type of ``near neighbor graph'': For a given set $S$ of points, define the ``$\theta_k$-graph of $S$'' to be the graph in which each point $p_i$ of $S$ is joined to the closest point of $S$ to it in each of the $k$ {\em sectors} with respect to $p$, where the sectors are defined to arise from a partition of the plane into $k$ equal-angled (angle $2\pi/k$) cones with apex at $p_i$, such that one of the cone boundary rays points in the $+y$ direction (so that all sets of sectors defined by the $n$ points are ``aligned'' with a common ``north''). The $\theta_1$-graph of $S$ is again the usual NNG (assuming no degeneracy), so it is planar. We asked about the planarity of the $\theta_2$-graph. At first, we thought it might be planar, but then realized that the construction of the subdivision of $K_5$ showing nonplanarity of $NNG_2(S)$ should also show nonplanarity of the $\theta_2$-graph. Joe then defined another natural near neighbor graph for a set of ``well separated points''. We say that $S$ is {\em well separated} if the distance between any two points of $S$ is at least 1. For a well separated set $S$ of $n$ points in the plane, define the $R$-graph of $S$ to be the graph whose nodes are the points $S$ and whose edges join each $p_i$ of $S$ to each other point $p_j$ that is at distance at most $R$ from $p_i$. For what values of $R$ is the $R$-graph planar/noncrossing? Again, obviously the case of $R=1$ is planar, since the only edges in the 1-graph are (some of the) edges that correspond to nearest neighbors. For $R=\sqrt{2}$, the $R$-graph may have crossing edges: let $S$ be the four corners of a unit square, then the $R$-graph is $K_4$, drawn with two crossing edges. We then also argued that if $R<\sqrt{2}$, the $R$-graph has no crossing edges. (If two edges cross, look at the associated convex quadrilateral. One of the corners has angle at least 90 degrees. Look at the triangle defined by the two edges incident on this corner; each of these two edges is at least length 1 (by definition of well separated). The edge opposite this corner, which purports to be an edge of the $R$-graph, is of length at least $\sqrt{2}$, a contradiction. Here is a remaining question: For values of $R\geq \sqrt{2}$, is the $R$-graph planar? (The unit square example yields a planar graph ($K_4$), two of whose edges cross.) Another possible question: What is the complexity of finding the largest (in terms of number of edges) noncrossing (or planar) subgraph of $NNG_k(S)$ or the $\theta_k$-graph? --Dxnq1zWXvFF0Q93v-- From abasu@cs.sunysb.edu Sat Jan 29 20:06:04 2005 Return-Path: Received: from compserv1 (compserv1 [130.245.1.44]) by sbcs.cs.sunysb.edu (8.12.3/8.12.3) with ESMTP id j0U162Vi029067; Sat, 29 Jan 2005 20:06:03 -0500 (EST) Date: Sat, 29 Jan 2005 20:06:04 -0500 (EST) From: Amitabh Basu X-X-Sender: abasu@compserv1 To: Joseph Mitchell cc: Yue Wang , skiena@cs.sunysb.edu, bender@cs.sunysb.edu, george@georgehart.com, ghart@optonline.net, alexmohr@joepc.ams.sunysb.edu, Esther Arkin Subject: Re: About today's seminar notes In-Reply-To: <20050129173208.GA12231@joepc> Message-ID: References: <20050129173208.GA12231@joepc> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Length: 1225 Status: RO Hi all, I just wanted to add an addendum to the problem regarding the "well-separated points" where we connect the points to all points within R. The same rule of R <= sqrt(2) works for even planarity (not just crossing). Clearly, if its non-crossing, it has to be planar for R<=sqrt(2). For R>=sqrt(2), we use prof. Skiena's "cloud points" construction of the K-5 subdivision, using the 4-point-square crossing gadget for the crossings in K-5. we just have to be a little careful about putting the points in such a way, so that the diagonals cross at 90 degrees for us to be able to insert the crossing gadget. I hope I didnt overlook something basic..... Best Regards, Amitabh. On Sat, 29 Jan 2005, Joseph Mitchell wrote: > Hi Yue! > > Thanks for agreeing to scribe! > > Indeed, yes, I did jot down some notes of my own > about the discussions yesterday. > Feel free to use this as a starting point for any of your own > notes. > > Joe > > > On Fri, Jan 28, 2005 at 04:07:29PM -0500, Yue Wang wrote: > > hi, Professor, > > > > Do you have any materials about the problem you said in today's > > seminar? If yes, I want to refer to them in order to scribe the notes. > > Thanks a lot!:) > > > > Best wishes, > > Yue >