` snoeyink@cs.ubc.ca`

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.

- 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.

- maxdepth.ps.gz (97K)
Efficient algorithms for maximum regression depth

van Kreveld, Mitchell, Rousseeuw, Sharir, Snoeyink, Speckmann

- diamond.ps.gz (270K)
On Exclusion Regions for Optimal Triangulations

Drysdale, McElfresh, Snoeyink (Scot, Scott, and Scott)

invited 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

Accepted to 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)

- 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. - rulerfold.ps.gz (353K--due to figure fonts)
Folding rulers inside triangles.

Marc van Kreveld, Jack Snoeyink, and Sue Whitesides.

{Discrete \& Computational Geometry}, 15(3):265--296, 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.

-- Jack Snoeyink (snoeyink@cs.ubc.ca)