Xref: utzoo comp.graphics:8591 comp.databases:4203
Path: utzoo!attcan!uunet!aplcen!uakari.primate.wisc.edu!gem.mps.ohio-state.edu!tut.cis.ohio-state.edu!mailrus!purdue!haven!mimsy!tank!eecae!cps3xx!flynn
From: flynn@pixel.cps.msu.edu (Patrick J. Flynn)
Newsgroups: comp.graphics,comp.databases
Subject: Re: Graphics data structure info request
Keywords: data-structures,closest-point
Message-ID: <5482@cps3xx.UUCP>
Date: 22 Nov 89 01:29:51 GMT
References: <3905@nicmad.UUCP>
Sender: usenet@cps3xx.UUCP
Organization: pxls wth n vwls
Lines: 25

[my apologies if you see this twice; the first posting was truncated and
 I am trying to cancel & repost...]

In article <3905@nicmad.UUCP> burton@nicmad.UUCP (Kevin Burton) writes:
>I have been considering for quite some time an efficient data structure
>for 2-D objects. By efficient I mean that the closest object or objects
>to a given object can be found very quickly and objects can be added and
>deleted easily. There are many structures that lend themselves very well
>to points (eg binary trees, B-trees, Delaunay triangulation ...) but I
>am unaware of any that explicitly deal with two dimensional objects. The
>quad-tree has the general flavor of the structure I am looking for but
>it seems too "raster" oriented to be adapted. Does anybody have any infor-
>mation, opinions, advice  ?

Hanan Samet from Maryland has a new book out entitled... [rustle,
rustle...] "The Design and Analysis of Spatial Data Structures",
published by Addison-Wesley, copyright 1990 (!).  I don't have the ISBN
number handy.  There is a companion volume on applications that hasn't
shown up in our bookstore yet.  The "Design" book discusses data
structures for 2D and 3D objects, focusing on tree-structures of
various sorts.  While I haven't done a thorough reading, it seems like
a very nice treatment of a variety of useful techniques.  There is a
HUGE bibliography.
--
Patrick Flynn, CS, Mich. State U., flynn@cps.msu.edu