Jack Snoeyink

The reflex-free hull (2008)

To investigate the parameters of the protein design problem that we are exploring in collaboration with biochemists, we have developed a tool that uses inverse kinematics to support moving small...

Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Jack Snoeyink

We propose a hull operator, the reflex-free hull, that allows us to define a 3D analogue to bays in polygons. The reflex-free hull allows a rich set of topological types, yet for polyhedral input...

Abstract Testing Shortcuts to Maintain Simplicity in Subdivision Simplification (2008)

Craig Falls, Yuanxin Liu, Jack Snoeyink, Diane Souvaine

Cartographers collect more data than they need,and so must simplify coastlines,boundaries,and other linear features to display a map at a given scale. Many simplification methods,however,can...

with the greedy flip algorithm (2008)

Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, Jack Snoeyink

enumerating pseudo-triangulations

1 Delineating Boundaries for Imprecise Regions ∗ (2008)

Iris Reinbacher, Marc Benkert, Marc Kreveld, Jack Snoeyink, Alexander Wolff, ...

In geographic information retrieval, queries often name geographic regions that do not have a well-defined boundary, such as “Southern France. ” We provide two algorithmic approaches to the...

Representation, I.6.9.g Visualization techniques and (2008)

Hamish Carr, Torsten Möller, Jack Snoeyink

Abstract — We review schemes for dividing cubic cells into simplices (tetrahedra) for interpolating from sampled data to IR 3, present visual and geometric artifacts generated in isosurfaces and...

Downloaded from (2008)

Kimberly Noonan, Jack Snoeyink, Kimberly Noonan, Jack Snoeyink

To investigate the parameters of the protein design problem that we are exploring in collaboration with biochemists, we have developed a tool that uses inverse kinematics to support moving small...

www.cs.uu.nl Delineating Boundaries for Imprecise Regions ∗ (2008)

Iris Reinbacher, Marc Benkert, Marc Van Kreveld, Jack Snoeyink, Alexander Wolff, ...

In geographic information retrieval, queries often utilize names of geographic regions that do not have a well-defined boundary, such as “Southern France. ” We provide two classes of algorithms...

Streaming Compression of Triangle Meshes (abstract) (2008)

Martin Isenburg, Peter Lindstrom, Jack Snoeyink

of compressor

Rapid Determination of Local Structural Features Common to a Set of Proteins (2008)

Jun Huan, Deepak B, Jinze Liu, Jan Prins, Jack Snoeyink, Er Tropsha, ...

Traditionally, protein structure comparison has focused on global similarity between two structures. Recent research has focused on finding local structural features in common among a group of...

Streaming Compression of Triangle Meshes (2008)

M. Desbrun, H. Pottmann (editors, Martin Isenburg, Peter Lindstrom, Jack Snoeyink

Current mesh compression schemes encode triangles and vertices in an order derived from systematically traversing the connectivity graph. These schemes struggle with gigabyte-sized mesh input where...

CAD’04, www.cadconferences.com Lossless Compression of Floating-Point Geometry (2008)

Martin Isenburg, Peter Lindstrom, Jack Snoeyink

The geometric data sets found in scientific and industrial applications are often very detailed. Storing them using standard uncompressed formats results in large files that are expensive to store...

Abstract Counting (2008)

Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, Jack Snoeyink

and enumerating pointed pseudo-triangulations

DISTANCE-BASED IDENTIFICATION OF STRUCTURE MOTIFS IN PROTEINS USING CONSTRAINED FREQUENT SUBGRAPH MINING (2008)

Jun Huan, Deepak B, Jan Prins, Jack Snoeyink, Er Tropsha, Wei Wang

Structure motifs are amino acid packing patterns that occur frequently within a set of protein structures. We define a labeled graph representation of protein structure in which vertices correspond...

Streaming Extraction of Elevation Contours from LIDAR Points (2008)

Martin Isenburg, Yuanxin Liu, Jack Snoeyink

Air-borne laser range scanning technology (LIDAR) is able to quickly generate massive amounts of densely spaced points that sample the elevation of a terrain. We describe a streaming technique that...

Abstract Graph Coding and Connectivity Compression (2008)

On the non-redundancy of split offsets in degree coding (2008)

This paper looks at the theoretic roots of current connectivity compression schemes to establish a visual framework within which the differences and similarities of various scheme become intuitive....

Optimal Algorithms to Embed Trees in a Point Set Prosenjit Bose y (2007)

The connectivity coder by Touma and Gotsman encodes a planar triangulation through a sequence of vertex degrees and occasional "split" symbols that have an associated offset value. It has...

4D Data Visualization Using Iso-surfaces and a Control Plane (2007)

We present optimal \Theta(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained...

Lutz Kettner, Jarek Rossignac, Jack Snoeyink

ability to efficiently analyze large data sets from a four-dimensional (4d) space-time domain. These

Safe Sets for Line Simplication (2007)

Andrea Mantler, Jack Snoeyink

Line simplication algorithms common in Geographic Information Systems (GIS) treat linear features in isolation, resulting in lines intersecting or lines moving past features. This is a problem for...

Selecting Independent Vertices for Terrain Simplification (2007)

Bernd Jünger, Jack Snoeyink

In this paper we investigate decimation algorithms for simplifying triangulated terrain models in order to support progressive transmission of GIS terrain models over the web. We report on...

Medial Axis Generalization of River Networks (2007)

Michael McAllister, Jack Snoeyink

We examine some benefits of using the medial axis as a centerline for rivers and lakes: One benefit, automatic centerline generation, has been used for many years. We show that additional benefits...

Removing degeneracies by perturbing the problem or perturbing the world (2007)

Pierre Alliez, Olivier Devillers, Jack Snoeyink

We describe two problem-specic approaches to remove geometric degeneracies that we call perturbing the problem and perturbing the world. Using the example of Delaunay triangulation, we show that...

Optimal Algorithms to Embed Trees in a Point Set Prosenjit Bose (2007)

Optimal Algorithms to Embed Trees in a Point Set Prosenjit Bose (2007)

We present optimal \Theta(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted tree embeddings and degree-constrained...

David Avis, Thomas C. Shermer, Jack Snoeyink, Godfried Toussaint

We present optimal \Theta(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained...

Prosenjit Bose (2007)

1

Prosenjit Bose 3 (2007)

Pankaj Agarwal, Mark De Berg, Katrin Dobrint, Marc Van Kreveld, Mark Overmars, Marko De Groot, ...

Triangulated surfaces are often used to represent terrains in Geographic Information Systems (GIS); one of the primary computations on terrains is determining drainage networks. Under natural...

Optimal Algorithms to Embed Trees in a Point Set Prosenjit Bose (2007)

Simon Kahan, Jack Snoeyink

Abstract. We present optimal \Theta(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted tree embeddings and degree-constrained...

Superquadratic (2007)

the bit complexity of minimum link paths:

. Our algorithm runs in O((n + f)log (2007)

Timothy M. Chan, Jack Snoeyink, Chee-keng Yap

In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E 4

Hamish Carr, Jack Snoeyink, Ulrike Axen

We show that contour trees can be computed in all dimensions by a simple algorithm that merges two trees. Our algorithm extends, simplifies, and improves work of Tarasov and Vyalyi and of van Kreveld...

and (2007)

Received received date Revised revised date Communicated by Editor's name We show that a decomposition of a simple polygon having n vertices, r of which are reflex, into a minimum number of...

Chong Zhu, Gopalakrishnan Sundaram, Jack Snoeyink

Sariel Har-peled, Timothy M. Chan, Boris Aronov, Dan Halperin, Jack Snoeyink

This note considers the complexity of a free region in the configuration space of a polygonal robot translating amidst polygonal obstacles in the plane. Specifically, given polygonal sets P and Q...

Prosenjit Bose 3 (2007)

Pankaj Agarwal, Mark De Berg, Katrin Dobrint, Marc Van Kreveld, Mark Overmars, Marko De Groot, ...

Triangulated surfaces are often used to represent terrains in Geographic Information Systems (GIS); one of the primary computations on terrains is determining drainage networks. Under natural...

2 (2007)

The problem of generating "random " geometric objects is motivated by the need to generate test instances for geometric algorithms. We examine the specific problem of generating a...

Jean-Daniel Boissonnat (2007)

J. E. Hershberger, J. S. Snoeyink, Correspondence Address, Jack Snoeyink

Efficient algorithms for line and curve segment intersection using restricted predicates

Theorems (2007)

Portions of this research were supported by DEC Systems Research Center. 2

Marc Van Kreveld, Jack Snoeyink, Sue Whitesides

An l-ruler is a chain of n links, each of length l. The links, which are allowed to cross, are modelled by line segments whose endpoints act as joints. A given configuration of an l-ruler is said to...

Abstract (2007)

Van Kreveld, Micha Sharir, Jack Snoeyink, Peter Rousseeuw, Bettina Speckmann

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual...

z (2007)

Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, Jack Snoeyink

We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions. Given an n-vertex polygonal curve P in IR

The Arithmetic Precision of Ray-Polygon Intersection Testing (2007)

The Reflex-Free Hull # Hee-kap Ahn Utrecht University (2007)

By looking for algorithms that require minimum arithmetic precision, we obtain a simple ray-polygon intersection test that more easily handles degenerate cases. 1

Siu-wing Cheng, Otfried Cheong, Jack Snoeyink

We define a reflex-free hull in three dimensions as an intersection of reflex-free sets. The reflex-free hull allows a rich set of topological types, yet for polyhedral input with n edges, it remains...

Heaphull? (2007)

Andrea Mantler, Jack Snoeyink

We present a planar convex hull algorithm, Heaphull, whose main data structure is a kinetic heap. We can limit the number of times a point needs to move up in the heap to establish that O(n lg n)...

The reflex-free hull (2007)

Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Jack Snoeyink

We define a reflex-free hull in three dimensions as an intersection of reflex-free sets. The reflex-free hull allows a rich set of topological types, yet for polyhedral input with n edges, it remains...

Lutz Kettner, David Kirkpatrick, Andrea Mantler, Jack Snoeyink, Bettina Speckmann, Fumihiko Takeuchi

We show that every set of n points in general position has a minimum pseudo-triangulation whose maximum vertex degree is ve. In addition, we demonstrate that every point set in general position has a...

247 Session C7 12th Canadian Conference on Computational Geometry Spirale Reversi: Reverse decoding of the Edgebreaker encoding (2007)

In this paper we investigate decimation algorithms for simplifying triangulated terrain models in order to support progressive transmission of GIS terrain models over the web. We report on...

Prosenjit Bose 2 (2007)

David Avis, Thomas C. Shermer, Jack Snoeyink, Godfried Toussaint, Binhai Zhu

Let K be a convex polytope in R d, let h(x) be the hyperplane consisting of all points with first coordinate equal to x, and let A(x) be the area (or volume, if d? 3) of the section K "...

Some Aperture-Angle Optimization Problems (2007)

We present a simple linear time algorithm for decoding Edgebreaker encoded triangle meshes in a single traversal. The Edgebreaker encoding technique, introduced in [5], encodes the connectivity of...

Prosenjit Bose, Ferran Hurtado-Diaz, Elsa Omana-Pulido, Jack Snoeyink, Godfried T. Toussaint

Let P and Q be two disjoint convex polygons in the plane with m and n vertices, respectively. Given a point x in P, the aperture angle of x with respect to Q is defined as the angle of the cone that:...

et calcul symbolique (2007)

Pierre Alliez, Pierre Alliez, Olivier Devillers, Olivier Devillers, Jack Snoeyink, Jack Snoeyink, ...

Removing degeneracies by perturbing the

MolProbity: all-atom contacts and structure validation for proteins and nucleic acids (2007)

Davis, Ian W., Leaver-Fay, Andrew, Chen, Vincent B., Block, Jeremy N., Kapral, Gary J., Wang, Xueyi, ...

MolProbity is a general-purpose web server offering quality validation for 3D structures of proteins, nucleic acids and complexes. It provides detailed all-atom contact analysis of any steric...

Nucleic Acids Research Advance Access published April 22, 2007 MolProbity: all-atom contacts and structure validation for proteins and nucleic acids (2007)

Ian W. Davis, Andrew Leaver-fay, Vincent B. Chen, Jeremy N. Block, Gary J. Kapral, Xueyi Wang, ...

MolProbity is a general-purpose web server offering quality validation for 3D structures of proteins, nucleic acids and complexes. It provides detailed all-atom contact analysis of any steric...

the University of British Columbia. (2007)

Marc Kreveld, Peter Rousseeuw, Micha Sharir, Jack Snoeyink, Bettina Speckmann, ...

M. Sharir supported by NSF Grants CCR-97-32101 and CCR-94-24398, by grants from the

Notes (2006)

Downloaded From, Email Alerting, Jack Snoeyink, Wei Wang, Alexander Tropsha

Structure-based function inference using protein family-specific fingerprints

Multiple structure alignment by optimal RMSD implies that the average structure is a consensus (2006)

Xueyi Wang, Jack Snoeyink

Root mean square deviation (RMSD) is often used to measure the difference between structures. We show mathematically that, for multiple structure alignment, the minimum RMSD (weighted at aligned...

Special Section on Automated Function Prediction (2006)

Deepak B, Jun Huan, Jinze Liu, Jan Prins, Jack Snoeyink, Wei Wang, ...

fingerprints

Generating raster DEM from mass points via TIN streaming (2006)

Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink, Tim Thirion

Abstract. It is difficult to generate raster Digital Elevation Models (DEMs) from terrain mass point data sets too large to fit into memory, such as those obtained by LIDAR. We describe prototype...

Generating raster DEM from mass points via TIN streaming (2006)

Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink, Tim Thirion

Abstract. It is difficult to generate raster Digital Elevation Models (DEMs) from terrain mass point data sets too large to fit into memory, such as those obtained by LIDAR. We describe prototype...

Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm (2006)

Brönnimann, Hervé, Kettner, Lutz, Pocchiola, Michel, Snoeyink, Jack

This paper studies pseudo-triangulations for a given point set in the plane. Pseudo-triangulations have many properties of triangulations, and have more freedom since polygons with more than three...

Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm (2006)

Brönnimann, Hervé, Kettner, Lutz, Pocchiola, Michel, Snoeyink, Jack

This paper studies pseudo-triangulations for a given point set in the plane. Pseudo-triangulations have many properties of triangulations, and have more freedom since polygons with more than three...

Structure-based function inference using protein family-specific fingerprints (2006)

Bandyopadhyay, Deepak, Huan, Jun, Liu, Jinze, Prins, Jan, Snoeyink, Jack, Wang, Wei, ...

We describe a method to assign a protein structure to a functional family using family-specific fingerprints. Fingerprints represent amino acid packing patterns that occur in most members of a family...

Lossless compression of predicted floating-point geometry (2005)

Martin Isenburg, Peter Lindstrom, Jack Snoeyink

The size of geometric data sets in scientific and industrial applications is constantly increasing. Storing surface or volume meshes in standard uncompressed formats results in large files that are...

Comparing Graph Representations of Protein Structure for Mining Family-Specific Residue-Based Packing Motifs (2005)

Jun Huan, Deepak Bandyopadhyay, Wei Wang, Jack Snoeyink, Jan Prins, Alexander Tropsha

We find recurring amino-acid residue packing patterns, or spatial motifs, that are characteristic of protein structural families, by applying a novel frequent subgraph mining algorithm to graph...

Comparing Graph Representations of Protein Structure for Mining Family-Specific Residue-Based Packing Motifs (2005)

Jun Huan, Deepak B, Wei Wang, Jack Snoeyink, Jan Prins, Er Tropsha

We find recurring amino-acid residue packing patterns, or spatial motifs, that are characteristic of protein structural families, by applying a novel frequent subgraph mining algorithm to graph...

An adaptive dynamic programming algorithm for the side chain placement problem (2005)

A. Leaver-fay, B. Kuhlman, J. Snoeyink, Andrew Leaver-fay, Brian Kuhlman, Jack Snoeyink

Larger rotamer libraries, which provide a fine grained discretization of side chain conformation space by sampling near the canonical rotamers, allow protein designers to find better conformations,...

Counting and enumerating pointed pseudo-triangulations with the greedy flip algorithm (2005)

Brönnimann, Hervé, Kettner, Lutz, Pocchiola, Michel, Snoeyink, Jack, Demetrescu, Camil, Tamassia, Roberto, ...

This paper studies (pointed, or minimal) pseudo-triangulations for a given point set in the plane. Pseudo-triangulations have many properties of triangulations, and have more freedom since polygons...

The Reflex-Free Hull (2004)

Ahn, Hee-Kap, Cheng, Siu-Wing, Cheong, Otfried, Snoeyink, Jack

We propose a hull operator, the reflex-free hull, that allows us to define a 3D analogue to bays in polygons. The reflex-free hull allows a rich set of topological types, yet for polyhedral input...

A 2-chain can interlock with a k-chain (2004)

Glass, Julie, Langerman, Stefan, O'Rourke, Joseph, Snoeyink, Jack, Zhong, Jianyuan K.

One of the open problems posed in [3] is: what is the minimal number k such that an open, flexible k-chain can interlock with a flexible 2-chain? In this paper, we establish the assumption behind...

Encoding volumetric grids for streaming isosurface extraction (2004)

Ajith Mascarenhas, Martin Isenburg, Valerio Pascucci, Jack Snoeyink

Simplifying flexible isosurfaces using local geometric measures (2004)

Hamish Carr, Jack Snoeyink

rendered isosurface current isovalue

Simplifying flexible isosurfaces using local geometric measures (2004)

Hamish Carr, Jack Snoeyink

rendered isosurface current isovalue

Time-varying reeb graphs for continuous space-time data (2004)

Herbert Edelsbrunner, John Harer, Ajith Mascarenhas, Valerio Pascucci, Jack Snoeyink

The Reeb graph is a useful tool in visualizing real-valued data obtained from computational simulations of physical processes. We characterize the evolution of the Reeb graph of a time-varying...

Mining spatial motifs from protein structure graphs (2004)

Jun Huan, Wei Wang, Deepak B, Jack Snoeyink, Jan Prins, Alex Tropsha

Finding recurring structural features among proteins three-dimensional (3D) structures is an important problem in bioinformatics. In this paper we apply a novel subgraph mining algorithm to three...

Mining Protein Family Specific Residue Packing Patterns from Protein Structure Graphs (2004)

Jun Huan, Wei Wang, Deepak B, Jack Snoeyink, Jan Prins, Alexander Tropsha

Finding recurring residue packing patterns, or spatial motifs, that characterize protein structural families is an important problem in bioinformatics. To this end, we apply a novel frequent subgraph...

Lossless compression of floating-point geometry (2004)

M. Isenburg, P. Lindstrom, J. Snoeyink, Martin Isenburg, Peter Lindstrom, Jack Snoeyink

Approved for public release; further dissemination unlimited

Encoding volumetric grids for streaming isosurface extraction (2004)

Ajith Mascarenhas, Martin Isenburg, Valerio Pascucci, Jack Snoeyink

A 2-CHAIN CAN INTERLOCK WITH A k-CHAIN (2004)

Julie Glass, Stefan Langerman, Jack Snoeyink, K. Zhong

Abstract. One of the open problems posed in [3] is: what is the minimal number k such that an open, flexible k-chain can interlock with a flexible 2-chain? In this paper, we establish the assumption...

Spanning Trees Crossing Few Barriers (2003)

Asano, Tetsuo, De Berg, Mark, Cheong, Otfried, Guibas, Leonidas J., Snoeyink, Jack, Tamaki, Hisao

We consider the problem of finding low-cost spanning trees for sets of $n$ points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a...

The Safari Interface for Visualizing Time-dependent Volume Data Using Iso-surfaces and Contour Spectra (2003)

Kettner, Lutz, Rossignac, Jarek, Snoeyink, Jack

We describe a geometric basis for the visualization of time-varying volume data of one or several variables as they occur in scientific and engineering applications. We demonstrate a prototype...

Tight Degree Bounds for Pseudo-triangulations of Points (2003)

Kettner, Lutz, Kirkpatrick, David, Mantler, Andrea, Snoeyink, Jack, Speckmann, Bettina, Takeuchi, Fumihiko

We show that every set of $n$ points in general position has a minimum pseudo-triangulation whose maximum vertex degree is five. In addition, we demonstrate that every point set in general position...

Computing a (1 + ffl)-Approximate Geometric Minimum-Diameter Spanning Tree (2003)

Michael J. Spriggs, J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, Jack Snoeyink

Abstract Given a set P of points in the plane, a geometric minimum-diameter spanning tree (GMDST)of P is a spanning tree of P such that the longest path through the tree is minimized. Forseveral...

ProcessingSingG2 A new Paradigm for Out-of-Core Processing on Large Meshes Martin Isenben (2003)

Stefan Gumhold And, Martin Isenburg, Stefan Gumhold, Jack Snoeyink

In this paper we introduce a new processing paradigm for meshes that are too large to fit entirely into main memory. We define the concept of a proce ssing se que that is essentially just a ordered...

Large mesh simplification using processing sequences (2003)

Martin Isenburg, Peter Lindstrom, Stefan Gumhold, Jack Snoeyink

Figure 1: Simplification with a fixed-size in-core buffer (pink). Via processing sequences, original triangles (gray) stream into the buffer and simplified triangles (gold) stream out. In this paper...

W-7405-Eng-48. Large Mesh Simplification using Processing Sequences (2003)

Livermore National Laboratory, M. Isenburg, P. Lindstrom, S. Gumhold, J. Snoeyink, Martin Isenburg, ...

In this paper we show how out-of-core mesh processing techniques can be adapted to perform their computations based on the new processing sequence paradigm [Isenburg and Gumhold 2003; Isenburg et al....

Interlocked open linkages with few joints (2002)

Erik D. Demaine, Cambridge Ma, Stefan Langerman, Jack Snoeyink

We advance the study of collections of open linkages in 3space that may be interlocked in the sense that the linkages cannot be separated without one bar crossing through another. We consider chains...

Ununfoldable polyhedra with convex faces (2002)

Marshall Bern, Erik D. Demaine, David Eppstein, Eric Kuo, Andrea Mantler, Jack Snoeyink

Unfolding a convex polyhedron into a simple planar polygon is a well-studied problem. In this paper, we study the limits of unfoldability by studying nonconvex polyhedra with the same combinatorial...

Testing Homotopy for Paths in the Plane ∗ (2002)

Inst Info, Comp Sci, Yuanxin Liu, Andrea Mantler, Jack Snoeyink

In this paper we present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For paths specified by n line...

Computing a (1+ɛ)-approximate geometric minimum-diameter spanning tree. Private communication (2002)

Michael J. Spriggs, J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, Jack Snoeyink

Given a set P of points in the plane, a geometric minimum-diameter spanning tree (GMDST) of P is a spanning tree of P such that the longest path through the tree is minimized. For several years, the...

Ununfoldable polyhedra with convex faces (2002)

Marshall Bern, Erik D. Demaine, David Eppstein, Eric Kuo, Andrea Mantler, Jack Snoeyink

Ununfoldable polyhedra with convex faces (2002)

Marshall Bern, Erik D. Demaine, Eric Kuo, Andrea Mantler, Jack Snoeyink

Unfolding a convex polyhedron into a simple planar polygon is a well-studied problem. In this paper, we study the limits of unfoldability by studying nonconvex polyhedra with the same combinatorial...

Interlocked open linkages with few joints (2002)

Erik D. Demaine, Stefan Langerman, Jack Snoeyink

We advance the study of collections of open linkages in 3-space that may be interlocked in the sense that the linkages cannot be separated without one bar crossing through another. We consider chains...

A one-step crust and skeleton extraction algorithm (2001)

Christopher Gold, Jack Snoeyink

We wish to extract the topology from scanned maps. In previous work [GNY96] this was done by extracting a skeleton from the Voronoi diagram, but this required vertex labelling and was only useable...

A lower bound for multicast key distribution (2001)

Jack Snoeyink, Subhash Suri, George Varghese

Abstract--With the rapidly growing importance of multicast in the Internet there have been recent proposal, such as RFC 2627, for scalable key distribution such that when the r, th user joins or...

Counting triangulations and pseudo-triangulations of wheels (2001)

Dana Randall, Gunter Rote, Francisco Santos, Jack Snoeyink

Motivated by several open questions on triangulations and pseudotriangulations, we give closed form expressions for the number of triangulations and the number of minimum pseudo-triangulations of n...

A prototype system for visualizing timedependent volume data (2001)

Lutz Kettner, Jack Snoeyink

This video shows a prototype system for the visualization of time-varying volume data of one or several variables as they occur in scientific and engineering applications. It partitions the data...

Counting triangulations and pseudo-triangulations of wheels (2001)

Dana Randall, Gunter Rote, Francisco Santos, Jack Snoeyink

Motivated by several open questions on triangulations and pseudotriangulations, we give closed form expressions for the number of triangulations and the number of minimum pseudo-triangulations of n...

A One-Step Crust and Skeleton Extraction Algorithm. (2001)

Christopher Gold, Jack Snoeyink

We wish to extract the topology from scanned maps. In previous work [GNY96] this was done by extracting a skeleton from the Voronoi diagram, but this required vertex labelling and was only useable...

Counting Triangulations and Pseudo-Triangulations of Wheels (2001)

Dana Randall College, Dana Randall, Francisco Santos, Günter Rote, Jack Snoeyink

Motivated by several open questions on triangulations and pseudotriangulations, we give closed form expressions for the number of triangulations and the number of minimum pseudo-triangulations of n...

Tight degree bounds for pseudo-triangulations of points (2001)

Lutz Kettner, David Kirkpatrick, Andrea Mantler, Jack Snoeyink, Bettina Speckmann, Fumihiko Takeuchi

We show that every set of n points in general position has a minimum pseudo-triangulation whose maximum vertex degree is five. In addition, we demonstrate that every point set in general position has...

CNOP - {A} Package for Constrained Network Optimization (2001)

Mehlhorn, Kurt, Ziegelmann, Mark, Buchsbaum, Adam L., Snoeyink, Jack

We present a generic package for resource constrained network optimization problems. We illustrate the flexibility and the use of our package by solving four applications: route planning, curve...

The Safari Interface for Visualizing Time-Dependent Volume Data Using Iso-Surfaces and a Control Plane (2001)

Kettner, Lutz, Rossignac, Jaroslaw R., Snoeyink, Jack

We describe a prototype interface for the visualization of time-varying volume data of one or several variables as they occur in scientific and engineering applications. We partition the data...

Removing degeneracies by perturbing the problem or perturbing the world (2000)

Removing degeneracies by perturbing the problem or perturbing the world (2000)

We describe two problem-specific approaches to remove geometric degeneracies that we call perturbing the problem and perturbing the world. Using as our primary examples 2-d and 3-d Delaunay...

Compact voronoi diagrams for moving convex polygons (2000)

We describe two problem-specific approaches to remove geometric degeneracies that we call perturbing the problem and perturbing the world. Using as our primary examples 2-d and 3-d Delaunay...

Leonidas Guibas, Jack Snoeyink, Li Zhang

We describe a kinetic data structure for maintaining a compact Voronoi-like diagram of convex polygons moving around in the plane. We use a compact diagram for the polygons, dual to the Voronoi,...

Compact voronoi diagrams for moving convex polygons (2000)

Leonidas Guibas, Jack Snoeyink, Li Zhang

We describe a kinetic data structure for maintaining a compact Voronoi-like diagram of convex polygons moving around in the plane. We use a compact diagram for the polygons, dual to the Voronoi,...

Spanning Trees Crossing Few Barriers (Algorithm Engineering as a New Paradigm) (1999)

Asano, Tetsuo, Berg, Mark De, Cheong, Otfried, Guibas, Leonidas J., Snoeyink, Jack, Tamaki, Hisao

Emerging Challenges in Computational Topology (1999)

Bern, Marshall, Eppstein, David, Agarwal, Pankaj K., Amenta, Nina, Chew, Paul, Dey, Tamal, ...

Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both...

Ununfoldable Polyhedra with Convex Faces (1999)

Bern, Marshall, Demaine, Erik D., Eppstein, David, Kuo, Eric, Mantler, Andrea, Snoeyink, Jack

Unfolding a convex polyhedron into a simple planar polygon is a well-studied problem. In this paper, we study the limits of unfoldability by studying nonconvex polyhedra with the same combinatorial...

The size of spanning disks for polygonal curves (1999)

Hass, Joel, Snoeyink, Jack, Thurston, William P.

Let $K$ be a closed polygonal curve in $\RR^3$ consisting of $n$ line segments. Assume that $K$ is unknotted, so that it is the boundary of an embedded disk in $\RR^3$. This paper considers the...

Emerging challenges in computational topology (1999)

Marshall Bern, Pankaj K. Agarwal, Nina Amenta, Paul Chew, Tamal Dey, David P. Dobkin, ...

Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies

Extracting consistent watersheds from digital river and elevation data (1999)

Finding the medial axis of a simple polygon in linear time (1999)

The Terrain Resources Inventory Mapping (TRIM) data standard in BC, Canada, includes specifications for river data and elevation data that are typically met by interpretation of stereo orthophotos....

Francis Chin, Jack Snoeyink, Cao An Wang

We give a linear-time algorithm for computing the medial axis of a simple polygon P, This answers a long-standing open question---previously, the best deterministic algorithm ran in O(n log n) time....

Spanning trees crossing few barriers (1999)

Tetsuo Asano, Mark Berg Cheong, Leonidas J. Guibas, Jack Snoeyink, Hisao Tamaki

We consider the problem of finding low-cost spanning trees for sets of n points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a...

Practical point-in-polygon tests using CSG representations of polygons (1999)

Robert J. Walker, Jack Snoeyink

We investigate the use of a constructive solid geometry (CSG) representation in testing if a query point falls inside a polygon; in particular, we use a CSG tree whose leaves correspond to halfplanes...

Queries with Segments in Voronoi Diagrams (1999)

Sergei Bespamyatnikh, Jack Snoeyink

In this paper we consider proximity problems in which the queries are line segments in the plane. We build a query structure that for a set of n points P can determine the closest point in P to a...

Practical Point-in-Polygon Tests Using CSG Representations of Polygons (1999)

Robert J. Walker, Jack Snoeyink

We investigate the use of a constructive solid geometry (CSG) representation of polygons in testing if points fall within them; this representation consists of a tree whose nodes are either Boolean...

Emerging Challenges in Computational Topology (1999)

Marshall Bern, David Eppstein, Pankaj K. Agarwal, Nina Amenta, Paul Chew, Tamal Dey, ...

Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both...

Efficient Algorithms for Maximum Regression Depth (1999)

Marc Van Kreveld, Peter Rousseeuw, Micha Sharir, Jack Snoeyink, Bettina Speckmann

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual...

Ununfoldable Polyhedra with Triangular Faces (1999)

Marshall Bern, Erik D. Demaine, David Eppstein, Eric Kuo, Andrea Mantler, Jack Snoeyink

We present a triangulated closed polyhedron that has no edge unfolding, and a triangulated open polyhedron that has no unfolding whatsoever.

Mesh Collapse Compression (1999)

Martin Isenburg Jack, Jack Snoeyink

We present a novel algorithm for encoding the topology of triangular meshes. A sequence of edge contract and divide operations collapses the entire mesh into a single vertex. This implicitly creates...

Extracting consistent watersheds from digital river and elevation data (1999)

Mesh Collapse Compression (1999)

The Terrain Resources Inventory Mapping (TRIM) data standard in BC, Canada, includes speci cations for river data and elevation data that are typically met by interpretation of stereo orthophotos. It...

Practical point-in-polygon tests using CSG representations of polygons (1999)

Abstract. We present a novel algorithm for encoding the topology of triangular meshes. A sequence of edge contract and divide operations collapses the entire mesh into a single vertex. This...

Robert J. Walker, Jack Snoeyink

We investigate the use of a constructive solid geometry (CSG) representation of polygons in testing if points fall within them; this representation consists of a tree whose nodes are either Boolean...

On the time bound for convex decomposition of simple polygons (1998)

Cartographic line simplification and polygon csg formul (1998)

We show that a decomposition of a simple polygon having n vertices, r of which are reAEex, into a minimum number of convex regions without the addition of Steiner vertices can be computed in O(n + r 2

John Hershberger, Correspondence Address, Jack Snoeyink, Jack Snoeyink

2

Efficiently Approximating Polygonal Paths in Three and Higher Dimensions (1998)

Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, Jack Snoeyink

We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions. Given an n-vertex polygonal curve P in IR d , d 3, we approximate P by another...

On the Time Bound for Convex Decomposition of Simple Polygons (1998)

Generalizing Ham Sandwich Cuts to Equitable Subdivisions (1998)

We show that a decomposition of a simple polygon having n vertices, r of which are reflex, into a minimum number of convex regions without the addition of Steiner vertices can be computed in O(n +...

Sergei Bespamyatnikh, David Kirkpatrick, Jack Snoeyink

We prove a generalization of famous Ham Sandwich Theorem for the plane. Given gn red points and gm blue points in the plane in general position, there exists a subdivision of the plane into g...

On the Time Bound for Convex Decomposition of Simple Polygons (1998)

Efficiently Approximating Polygonal Paths in Three and Higher Dimensions (1998)

We show that a decomposition of a simple polygon having n vertices, r of which are reflex, into a minimum number of convex regions without the addition of Steiner vertices can be computed in O(n + r...

Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, Jack Snoeyink

We present efficient algorithms for solving polygonal -path approximation problems in three and higher dimensions. Given an n-vertex polygonal curve P in IR d , d 3, we approximate P by another...

Efficient Algorithms for Line and Curve Segment Intersection Using Restricted Predicates (1998)

Jean-Daniel Boissonnat, Jack Snoeyink

We consider whether restricted sets of geometric primitives support efficient algorithms to solve line and curve segment intersection problems in the plane. Our restrictions are based on the notion...

The size of spanning disks for PL Knots. (1998)

Joel Hass, Jack Snoeyink, William P. Thurston

For each integer n ? 1 we construct a closed unknotted PL curve Kn in R 3 having less than 33n edges with the property that any PL triangluated disk spanning the curve contains at least 2 n...

Removing Degeneracies by Perturbing the Problem or the World (1997)

Removing Degeneracies by Perturbing the Problem or the World (1997)

We describe two problem-specific approaches to remove geometric degeneracies that we call {\it perturbing the problem} and {\it perturbing the world}. Using as our primary examples 2-d and 3-d...

Using CSG Representations of Polygons for Practical Point-in-Polygon Tests (Extended Abstract) (1997)

We describe two problem-specific approaches to remove geometric degeneracies that we call {\it perturbing the problem} and {\it perturbing the world}. Using as our primary examples 2-d and 3-d...

Robert Walker, Jack Snoeyink

) Robert Walker Jack Snoeyink Department of Computer Science University of British Columbia 2366 Main Mall Vancouver, BC, Canada V6T 1Z4 Telephone: +1 604 822 3061 Fax: +1 604 822 5485 Email:...

Optimal Algorithms to Embed Trees in a Point Set (1997)

Prosenjit Bose, Michael Mcallister, Jack Snoeyink

We present optimal ##n log n# time algorithms to solvetwo tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained embeddings. In...

Linear-time reconstruction of Delaunay triangulations with applications (1997)

Jack Snoeyink, Marc Van Kreveld

Many of the computational geometers' favorite data structures are planar graphs, canonically determined by a set of geometric data, that take \Theta(n log n) time to compute. Examples include...

Primal Dividing and Dual Pruning: Output-Sensitive Construction of 4-d Polytopes and 3-d Voronoi Diagrams (1997)

Timothy M. Chan, Jack Snoeyink, Chee-keng Yap

In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E 4 . Our algorithm runs in O((n + f)log 2 f) time and uses...

Linear-time reconstruction of Delaunay triangulations with applications (1997)

Jack Snoeyink, Marc Van Kreveld

Many of the computational geometers' favorite data structures are planar graphs, canonically determined by a set of geometric data, that take \Theta(n log n) time to compute. Examples include...

Optimal Algorithms to Embed Trees in a Point Set (1996)

Bose, Prosenjit, McAllister, Michael, Snoeyink, Jack

We present optimal \Theta(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained...

A compact piecewise-linear Voronoi diagram for convex sites in the plane (1996)

Michael Mcallister, David Kirkpatrick, Jack Snoeyink

In the plane, the post-ofice problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one-dimensional retract of the free space of a robot, are both...

On computing edges that are in all minimum-weight triangulations (1996)

Patrice Belleville, Mark Keil, Michael Mcallister, Jack Snoeyink

Given a set P of n points in the plane, we say that a triangle is empty if the intersection " P contains only the three vertices of. A triangulation of P is

Cross ratios and angles determine a polygon (1996)

Drainage queries in TINs: from local to global and back again (1996)

We prove that a unique simple polygon is determined, up to similarity, by the interior angles at its vertices and the cross-ratios of diagonals of any given triangulation. (The cross-ratio of a...

Sidi Yu, Marc Van Kreveld, Jack Snoeyink

This paper considers the cost of preprocessing a digital terrain model (DTM) represented as a triangulated irregular network (TIN) so that drainage queries---e.g., what is the watershed of a query...

Approximating Shortest Paths in Arrangements of Lines (1996)

Prosenjit Bose William, William Evans, David Kirkpatrick, Michael Mcallister, Jack Snoeyink

this paper, we consider shortest paths on an arrangement: Given a set L of n lines in the plane, and two points s and t that lie on lines of L, find a shortest path from s to t that is restricted to...

A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane (1996)

Michael McAllister, David Kirkpatrick, Jack Snoeyink

In the plane the post-office problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one-dimensional retract of the free space of a robot, are both...

A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane (1996)

Michael McAllister, David Kirkpatrick, Jack Snoeyink

In the plane, the post-office problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one-dimensional retract of the free space of a robot, are both...

Approximating Shortest Paths in Arrangements of Lines (1996)

Prosenjit Bose, William Evans, David Kirkpatrick, Michael McAllister, Jack Snoeyink

this paper, we study the problem of computing the shortest path between a pair of points on an arrangement of lines with respect to the Euclidean distance metric. Let L = f` 1 ; ` 2 ; : : : ; ` n g...

Folding Rulers inside Triangles (1996)

Marc Van Kreveld, Jack Snoeyink, Sue Whitesides

An l-ruler is a chain of n links, each of length l. The links, which are allowed to cross, are modelled by line segments whose endpoints act as joints. A given configuration of an l-ruler is said to...

Computing common tangents without a separating line (1995)

Two- and three-dimensional point location in rectangular subdivisions (1995)

Given two disjoint convex polygons in standard representations, one can compute outer common tangents in logarithmic time without rst obtaining a separating line. If the polygons are not disjoint,...

Mark De Berg, Marc Van Kreveld, Jack Snoeyink

We apply van Emde Boas-type stratified trees to point location problems in rectangular subdivisions in 2 and 3 dimensions. In a subdivision with n rectangles having integer coordinates from [0; U...

Computing the largest inscribed isothetic rectangle (1995)

David Hsu, Jack Snoeyink

In this paper, we give a logarithmic-time solution to a problem considered by Fischer and Hoffgen [2]: Given the list vertices of a convex polygon P in counterclockwise (ccw) order, stored in an...

Computing common tangents without a separating line (1995)

Tentative prune-and-search for computing fixed-points with applications to geometric computation (1995)

Given two disjoint convex polygons in standard representations, one can compute outer common tangents in logarithmic time without first obtaining a separating line. If the polygons are not disjoint,...

The Complexity of a Single Face of a Minkowski Sum (1995)

Abstract. Motivated by problems in computational geometry, this paper investigates the complexity of finding a fixed-point of the composition of two or three continuous functions that are defined...

Sariel Har-peled, Timothy M. Chan, Boris Aronov, Dan Halperin, Jack Snoeyink

This note considers the complexity of a free region in the configuration space of a polygonal robot translating amidst polygonal obstacles in the plane. Specifically, given polygonal sets P and Q...

Optimal algorithms to embed trees in a point set (1995)

Prosenjit Bose, Michael Mcallister, Jack Snoeyink

We present optimal Θ(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained embeddings. In...

An optimal algorithm for the on-line closest-pair problem (1994)

Christian Schwarz, Michiel Smid, Jack Snoeyink

problem

Computing minimum length paths of a given homotopy class (1994)

John Hershberger, Jack Snoeyink

In this paper, we show that the universal covering space of a surface can be used to unify previous results on computing paths in a simple polygon. We optimize a given path among obstacles in the...

Computing minimum length paths of a given homotopy class (1994)

Jack Snoeyik, John Hershberger, John Hershberger, Jack Snoeyink

the Netherlands t

Computing the Largest Inscribed Isothetic Rectangle (1994)

Helmut Alt, David Hsu, Jack Snoeyink

This paper describes an algorithm to compute, in \Theta(log n) time, a rectangle that is contained in a convex n-gon, has sides parallel to the coordinate axes, and has maximum area. With a slight...

Computing Common Tangents Without a Separating Line (1994)

David Kirkpatrick Jack, Jack Snoeyink

Given two disjoint convex polygons in standard representations, one can compute outer common tangents in logarithmic time without first obtaining a separating line. If the polygons are not disjoint,...

Counting and Reporting Red/Blue Segment Intersections (1993)

Larry Palazzi, Jack Snoeyink

We simplify the red/blue segment intersection algorithm of Chazelle et al: Given sets of n disjoint red and n disjoint blue segments, we count red/blue intersections in O(n log n) time using O(n)...

Tentative Prune-and-Search for Computing Fixed-Points with Applications to Geometric Computation (1993)