Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors (2009)
Jonathan Derryberry, Don Sheehy, Daniel D. Sleator, Maverick Woo
We present the first spatially adaptive data structure that answers approximate nearest neighbor (ANN) queries to points that reside in a geometric space of any constant dimension d. The Lt-norm...
SHAPE DEFORMATION IN CONTINUOUS MAP GENERALIZATION (2009)
Jeff Danciger, Satyan L. Devadoss, John Mugno, Don Sheehy, Rachel Ward
Abstract. Given a collection of regions on a map, we seek a method of continuously altering the regions as the scale is varied. This is formalized and brought to rigor as well-defined problems in...
Size complexity of volume meshes vs. surface meshes (2009)
Benoît Hudson, Gary L. Miller, Todd Phillips, Don Sheehy
Typical volume meshes in three dimensions are designed to conform to an underlying two-dimensional surface mesh, with volume mesh element size growing larger away from the surface. The surface mesh...
Size complexity of volume meshes vs. surface meshes (2009)
Benoît Hudson, Gary L. Miller, Todd Phillips, Don Sheehy
Typical volume meshes in three dimensions are designed to conform to an underlying two-dimensional surface mesh, with volume mesh element size growing larger away from the surface. The surface mesh...
A HOMOTOPIC APPROACH TO CARTOGRAPHIC GENERALIZATION (2008)
Jeff Danciger, Satyan L. Devadoss, John Mugno, Don Sheehy, Rachel Ward
Abstract. Given a collection of objects on a map, we seek a method of enlarging the objects over time so that these objects are still visible when the map is zoomed out. This question is brought to...
COMPATIBLE TRIANGULATIONS AND POINT PARTITIONS BY SERIES-TRIANGULAR GRAPHS (2008)
Jeff Danciger, Satyan L. Devadoss, Don Sheehy
Abstract. We introduce series-triangular graph embeddings and show how to partition point sets with them. This result is then used to prove an upper bound on the number of Steiner points needed to...
SHAPE DEFORMATION IN CONTINUOUS MAP GENERALIZATION (2008)
Jeff Danciger, Satyan L. Devadoss, John Mugno, Don Sheehy, Rachel Ward
Abstract. Given a collection of regions on a map, we seek a method of altering the regions over time so they are still visible when the map is scaled. This is formalized and brought to rigor as...
Approximate Center Points with Proofs (2008)
We present the Iterated-Tverberg algorithm, the first deterministic algorithm for computing an approximate center point of a set S ∈ R d with running time sub-exponential in d. The algorithm is a...
Cone Depth and the Center Vertex Theorem (2008)
Gary L. Miller, Todd Phillips, Don Sheehy
We generalize the Tukey depth to use cones instead of halfspaces. We prove a generalization of the center point theorem that for S ⊂ Rd, there is a point s ∈ S, with depth at least n d+1 for...
Fast Sizing Calculations for Meshing (2008)
Gary L. Miller, Todd Phillips, Don Sheehy
Provably correct algorithms for meshing difficult domains in three dimensions have been recently developed in the literature. These algorithms handle the problem of sharp angles (< π/2) between...
Cone Depth and the Center Vertex Theorem (2008)
Gary L. Miller, Todd Phillips, Don Sheehy
We generalize the Tukey depth to use cones instead of halfspaces. We prove a generalization of the Center Point Theorem that for S ⊂ Rd, there is a vertex s ∈ S, with depth at least n d+1 for...
Compatible Triangulations and Point Partitions by Series-Triangular Graphs (2005)
Danciger, Jeff, Devadoss, Satyan L., Sheehy, Don
We introduce series-triangular graph embeddings and show how to partition point sets with them. This result is then used to improve the upper bound on the number of Steiner points needed to obtain...
3.2 Standard Dominos in the Plane................... 8 (2005)
Don Sheehy, Advisor Kevin Wayne
In this paper, we give a combinatorial formalization that describes a wide range of related problems in the theory of tiling derived from the popular game of dominos. We show that determining if a...