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.