From:"Thomas A. McGlynn" <tam@silk.gsfc.nasa.gov>Date:Tue, 11 Feb 1997 17:26:13 -0500Newsgroups:sci.mathSubject:Delauney triangulation and points of intersections of lines

I've been building a method for resample pixel data which uses the Delauney triangulation of a set of points, but I have not been able to prove that it will work properly in a general case and I'd be interested if anyone could point me to appropriate references. The Delauney triangulation (i.e., the creation of triangular tiles with vertices at each of the points which cover the region in which the points are contained) has the property that the circumscribing circle for each triangle contains no other vertices of the triangulation within it. It's frequently used to do interpolations of irregularly sampled data, but that's not my interest. Suppose I have a Deluaney triangulation, T, of the set of points which comprise all the intersections between a set, L, of lines. T is a set of triangular tiles. What I need to show is that there is no triangle in T which is crossed by any of the lines L. Empirically I've found this to be true for the cases that I use, but I'm not clear how I'd prove it generally -- or if it is not true generally, whether there are any restrictions I can place on L to ensure that it is true. If anyone has any comments or can point me to appropriate references I'd be very grateful. Yours, Tom McGlynn tam@silk.gsfc.nasa.gov

From:Hans Kristian Ruud <hkr@ifi.uio.no>Date:19 Feb 1997 15:34:48 +0100Newsgroups:sci.mathSubject:Re: Delauney triangulation and points of intersections of lines

> Suppose I have a Deluaney triangulation, T, of > the set of points which comprise all the intersections between > a set, L, of lines. T is a set of triangular tiles. > What I need to show is that there is no triangle in T > which is crossed by any of the lines L. Well, I managed to come up with the following counterexample: draw 4 lines forming an elongated diamond, such that their intersection points are ABCD. A B C D Then draw a new line EF: A E B C F D The triangles BFC and BCE will belong to the Delauney triangulation, yet the line EF will intersect them. -- * Hans Kr. Ruud The noble art * * Kristine Bonnevies vei 15 of losing face * * 0592 ÅRVOLL may one day save * * Tlf. 22 65 22 34 (hjemme) 22 77 05 35 (jobb) the human race *