##
Interpolation Search for Point Cloud Intersection

##### Paper

The screen version is optimized for on-screen viewing:
color plots and hyperlinks.

The print version is optimized for printing: no color plots, no
hyperlinks.
##### Abstract

We present a novel algorithm to compute intersections of two point clouds.
It can be used to detect collisions between implicit surfaces defined by two
point sets, or to construct their intersection curves. Our approach utilizes
a proximity graph that allows for quick interpolation search of a common zero
of the two implicit functions.
First, pairs of points from one point set are constructed, bracketing the
intersection with the other surface. Second, an interpolation search along
shortest paths in the graph is performed. Third, the solutions are refined.
For the first and third step, randomized sampling is utilized.

We show that the number of evaluations of the implicit function and the
overall runtime is in O( log log N) in the average case, where N is the point
cloud size. The storage is bounded by O(N).

Our measurements show that we achieve a speedup by an order of magnitude
compared to a recently proposed randomized sampling technique for point cloud
collision detection.

##### Keywords

Collision detection, weighted least squares, proximity graphs, implicit surfaces.
##### BibTeX entry

@INPROCEEDINGS{Zach05
, author = "Jan Klein and Gabriel Zachmann"
, title = "Interpolation Search for Point Cloud Intersection"
, booktitle = "Proc. of WSCG 2005"
, pages = "163--170"
, month = jan # "31 -- " # feb # "7"
, year = 2005
, address = "University of West Bohemia, Plzen, Czech Republic"
, url = "http://www.gabrielzachmann.org/"
, ISBN = "80-903100-7-9"
}

##### In case of problems

In case of problems, please don't hesitate to
contact me.

(For instance, if your host is not registered by the world-wide Domain
Name Service (DNS), then you will not be able to ftp ...)
Gabriel Zachmann

Last modified:
Sat Sep 10 15:59:33 MDT 2005