From owner-theorynt@LISTSERV.NODAK.EDU Thu Apr 10 01:02:33 1997 Received: from CS.Stanford.EDU (CS.Stanford.EDU [171.64.64.64]) by robotics.Stanford.EDU (8.8.5/8.8.5) with ESMTP id BAA13170 for ; Thu, 10 Apr 1997 01:02:33 -0700 (PDT) Received: from listserv.nodak.edu (listserv.NoDak.edu [134.129.111.8]) by CS.Stanford.EDU (8.8.4/8.8.4) with ESMTP id AAA13854; Thu, 10 Apr 1997 00:51:36 -0700 (PDT) Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.21118220@listserv.nodak.edu>; Thu, 10 Apr 1997 2:51:46 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 529492 for THEORYNT@LISTSERV.NODAK.EDU; Thu, 10 Apr 1997 02:51:37 -0500 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.1B5CD210@listserv.nodak.edu>; Thu, 10 Apr 1997 2:51:36 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 529482 for THEORY-B@LISTSERV.NODAK.EDU; Thu, 10 Apr 1997 02:51:36 -0500 Received: from pollux.usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.1AD1C6E0@listserv.nodak.edu>; Thu, 10 Apr 1997 2:51:35 -0500 Received: (from ierardi@localhost) by pollux.usc.edu (8.8.4/8.8.4/usc) id AAA11995 for theory-b@listserv.nodak.edu; Thu, 10 Apr 1997 00:51:34 -0700 (PDT) Approved-By: Doug Ierardi Approved-By: Theory-B - TheoryNet Ongoing Seminars and Lectures Message-ID: <9704032249.AA15982@GEOMETRY.CIMS.NYU.EDU> Date: Thu, 10 Apr 1997 00:51:31 PDT Reply-To: Theory-B - TheoryNet Ongoing Seminars and Lectures , Ricky Pollack Sender: TheoryNet List From: Ricky Pollack Subject: [Theory-B] corrected announcement for 28th Computational Geometry Day (May 2) Comments: To: THEORY-B@LISTSERV.NODAK.EDU To: THEORYNT@LISTSERV.NODAK.EDU X-Mozilla-Status: 0001 Content-Length: 4020 New York University Courant Institute of Mathematical Sciences TWENTY EIGHTH COMPUTATIONAL GEOMETRY DAY Friday, May 2, 1996 Room 109, Warren Weaver Hall 251 Mercer St., New York, NY 10012 10.00--10.30 {\em Coffee (Warren Weaver Hall Lobby) 10:30--11:15 Pankaj K. Agarwal, Duke University Binary Space Partitions: Old and New Results 11:30--12:15 Marjorie Senechal, Smith College Periodicity Revisited 12:30--2:00 Lunch 2:00--3:00 Open Problem Session 3:00--3:45 Jack Snoeyink, University of British Columbia Good orders for incremental (re)constructions: How to hide geometric structure in flat files For more information contact:Richard Pollack (212) 998-3167 pollack@geometry.nyu.edu *********************************abstracts******************************* Binary Space Partitions: Old and New Results Pankaj K. Agarwal Binary space partition (BSP) is a hierarchical decomposition of space, widely used for several problems in computer graphics. Roughly speaking, BSP for a set of objects is a binary tree, each of whose nodes are associated with a convex region. The regions associated with the leaves of the tree form a convex decomposition of the space, and the interior of such a region does not intersect any input object. The first part of the talk surveys the known results on constructing a BSP of a set of objects in two and three dimensions. The second part of the talk discusses new algorithms for constructing a BSP for a set of orthogonal rectangles in 3D, for constructing a BSP of a set of triangles in 3-space, and for maintaining a BSP of a set of moving segments in the palne. Periodicity Revisited Marjorie Senechal A Delaunay set (or $(r,R)$ set) is a discrete set $X$ in $R^n$ such that each open ball of radius $r$ contains at most one point of $X$ and each closed ball of radius $R$ contains at least one point of $X$; obviously very general, they can be used to model structures as diverse as crystals and gases. We will discuss recent work of Lagarias and others on the relation between local configurations and global order in Delaunay sets. Good orders for incremental (re)constructions: How to hide geometric structure in flat files Jack Snoeyink Many of the computational geometers' favorite data structures are planar graphs that are canonically determined by a set of geometric data and that take $\Theta(n \log n)$ time to compute. Examples include 2-d Delaunay triangulation, trapezoidations of segments, and constrained Voronoi diagrams, and 3-d convex hulls. Given such a structure, one can determine a permutation of the data in $O(n)$ time such that the data structure can be reconstructed from the permuted data in $O(n)$ time by a simple incremental algorithm. This theorem has some amusing consequences. Consider terrain models based on the Delaunay triangulation in GIS (Geographic Information Systems). One can reorder a data file to "hide" the triangulation without disrupting other applications. One can even include "importance" in the ordering so the incremental reconstruction produces approximate terrain models as the data is read or received. To apply this to real data, input in degenerate position must be handled properly, even though the data structures may no longer be canonicaly defined. This becomes mathematically interesting, because standard pertubation schemes based on point indices do not apply. For the Delaunay triangulation, however, we can handle the degeneracies. Some theorems are joint work with Marc van Kreveld, and Java demos with Bernd Juenger.