Gzipped postscript versions of some recent papers
When you click on a file name your Web browser may start a postscript viewer
or may ask for a filename to save. In the latter case, pick a name ending
in .ps.gz, then gunzip that name to get a .ps file for printing or previewing.
If you have trouble, or need hardcopy, my email is
The ACM would like me to add that
the documents contained in these directories are included
by the contributing authors as a means to ensure timely
dissemination of scholarly and technical work on a
non-commercial basis. Copyright and all rights therein
are maintained by the authors or by other copyright
holders, notwithstanding that they have offered their
works here electronically. It is understood that all
persons copying this information will adhere to the terms
and constraints invoked by each author's copyright.
These works may not be reposted without the explicit
permission of the copyright holder.
GIS and GIS motivated work
- watershed.ps.gz (420K)
watershed.pdf (520K)
Extracting Consistent Watersheds
from Digital River and Elevation Data
Michael McAllister and Jack Snoeyink
1999 ASPRS Annual Conference
- Crust.pdf (3.9M)
Crust and Anti-Crust: A one-step boundary and skeleton extraction
algorithm
Christopher Gold and Jack Snoeyink
Our journal submission version of Chris' 1999 ACM SCG paper.
NOTE: this is PDF because the figures made the postscript too large.
- segint.ps.gz (100K)
Efficient algorithms for line and curve segment intersection
using restricted predicates
JD Boissonnat and J Snoeyink
1999 ACM Symp on Comp Geom. Invited to Comp Geom: Theory and Appl.
- juenger.ps.gz (120K)
Selecting Independent Vertices For Terrain Simplification
Bernd Juenger and Jack Snoeyink
In WSCG '98, Plzen, Cz
- reconstr.ps.gz (110K)
Linear-time reconstruction of Delaunay triangulations with applications
Jack Snoeyink, Marc van Kreveld
ESA '97: European Symp on Algorithms
We also had a poster at ACM SCG 97.
- fastbool.ps.gz (87K)
Cartographic Line Simplification and Polygon CSG Formulae
in O(n\log^* n) Time
John Hershberger, Jack Snoeyink
Workshop on Alg & Data Structures, 1997. Accepted to CGTA.
- drainage.ps.gz (87K)
Drainage Queries in TINs: From local to global and back again
Sidi Yu, Marc van Kreveld, Jack Snoeyink
7th Symp Spatial Data Handling, pages 13A.1--13A.14, 1996
- overlay.ps.gz (63K)
Further Comparison of Algorithms for Geometric
Intersection Problems
D. S. Andrews J. Snoeyink J. Boritz T. Chan
G. Denham J. Harrison C. Zhu
6th Int'l Symposium on Spatial Data Handling, Sept 1994.
- DPsimp
Speeding up the {Douglas-Peucker} line simplification algorithm.
John Hershberger and Jack Snoeyink.
In {\em Proc. 5th Intl. Symp. Spatial Data Handling}, pages 134--143.
{IGU} Commission on {GIS}, 1992.
Tech report version.
Ar archive of code (37K) (README at end) also
available.
Computational Geometry papers in the pipeline
- contree.ps.gz (200K)
Computing contour trees in all dimensions
Carr, Snoeyink, Axen, to appear in SODA'00
- maxdepth.ps.gz (97K)
Efficient algorithms for maximum regression depth
van Kreveld, Mitchell, Rousseeuw, Sharir, Snoeyink,
Speckmann, in ACM SCG '99
- diamond.ps.gz (270K)
On Exclusion Regions for Optimal Triangulations
Drysdale, McElfresh, Snoeyink (Scot, Scott, and Scott)
accepted to Disc Appl Math
- convdecomp.ps.gz (90K)
On the time bound for convex decomposition of simple polygons
Mark Keil and Jack Snoeyink
full version of abstract in 10th CCCG, accepted to IJCGA.
- crossrat.ps.gz (84K)
Cross-ratios and angles determine a polygon
Jack Snoeyink
In special issue of DCG on papers from 1998 ACM SCG
- ins-rect.ps.gz (50K)
Computing the largest inscribed isothetic rectangle.
H. Alt, D. Hsu, and J. Snoeyink.
Accepted to CGTA 1997. (Some figure fonts omitted to save space)
- nosep.ps.gz (61K)
Computing common tangents without a separating line
David Kirkpatrick, Jack Snoeyink
WADS 1995.
(
Code available)
Appeared in Computational Geometry
- Go to UBC CS technical reports
- medaxis.ps.gz (97K)
Finding the Medial Axis of a Simple Polygon in Linear Time
F. Chin, J. Snoeyink, C. Wang
Disc. Comp. Geom, 1999
- primal.ps.gz (97K)
Primal Dividing and Dual Pruning: Output-sensitive
construction of 4-d polytopes and 3-d {V}oronoi diagrams.
T. M.-Y. Chan, J Snoeyink., C.-K. Yap
DCG 1997
- erased.ps.gz (134K)
Erased Arrangements of Lines and Convex Decompositions of Polyhedra
J. Hershberger J. Snoeyink
Comp Geom: Theory and Applications, 1997
- rivercx.ps.gz (41K) The Complexity of
Rivers in Triangulated Terrains
P. Agarwal, M. de Berg, P. Bose, K. Dobrint, M. van Kreveld,
M. Overmars, M. de Groot, T. Roos, J. Snoeyink, S. Yu
8th CCCG, pages 325--329, 1996.
- bitcx.ps.gz (177K) On the bit complexity of
minimum link paths:
Superquadratic algorithms for problems solvable in linear time
S. Kahan, J. Snoeyink
ACM SCG, pages 151--158, 1996.
Accepted to special issue of CGTA.
- compliant.ps.gz (145K)
Efficiently Planning Compliant Motion in the Plane
J. Friedman J. Hershberger J. Snoeyink
SIAM J Comp, 25(3):562--599, 1996.
- mwtvideo.ps.gz (72K) On Computing
Edges That Are In All Minimum-Weight Triangulations
P. Belleville, M. Keil, M. McAllister, J. Snoeyink
Two-page description of video in ACM SCG '96 Video Review
306 point set for LMT-skeleton testing
(has colinearities).
- retract.ps.gz (140K)
A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the
Plane
Michael McAllister, David Kirkpatrick, Jack Snoeyink
{Discrete \& Computational Geometry}, 15:73--105, 1996.
- embtree.ps.gz (222K)
Optimal Algorithms to Embed Trees in a Point Set
Prosenjit Bose, Michael McAllister,Jack Snoeyink
Graph Drawing, LNCS 1027, pages 64--75. Springer-Verlag, 1996.
- random.ps.gz (95K)
Generating Random Polygons with Given Vertices
Chong Zhu, Gopalakrishnan Sundaram, Jack Snoeyink,
Joseph S. B. Mitchell
{CG T&A}, 6:277--290, 1996.
- minkcx.ps.gz (191K)
The complexity of a single face of a Minkowski sum.
Har-Peled, S., Chan, T.~M., Aronov, B., Halperin, D.,
and Snoeyink, J.
7th CCCG, 1995.
- stratptloc.ps.gz (77K)
Two- and three-dimensional point location in
rectangular subdivisions.
de~Berg, M., van Kreveld, M., and Snoeyink, J.
{\em Journal of Algorithms}, 18:256--277, 1995.
- tentative.ps.gz (86K)
Tentative Prune-and-Search for Computing Fixed-Points
with Applications to Geometric Computation
Kirkpatrick, D. and Snoeyink, J.
{\em Fundamenta Informatic\ae}, 22(4):353--370, 1995.
- closepair.ps.gz (52K)
An Optimal Algorithm for the On-Line Closest-Pair Problem
C. Schwarz, M. Smid, J. Snoeyink
Algorithmica 12(1), pages 18--29, 1994
- homotopy.ps.gz (226K)
Computing minimum length paths of a given homotopy class.
Hershberger, J. and Snoeyink, J.
{\em Computational Geometry: Theory and Applications} 4 (1994), 63--97.
- minlink.ps.gz (125K)
Approximating polygons and subdivisions with minimum-link paths.
Guibas, L.~J., Hershberger, J.~E., Mitchell, J. S.~B., and
Snoeyink, J.~S.
{\em International Journal of Computational Geometry \&
Applications}, 3(4):383--415, 1993.
--