2009
-
The Centervertex Theorem for Wedges
Gary L. Miller,
Todd Phillips,
Donald R. Sheehy,
CCCG: The Canadian Conference in Computational Geometry
2009
There are many depth measures on point sets that yield centerpoint theorems.
These theorems guarantee the existence of points of a specified depth, a kind of geometric median.
However, the deep point guaranteed to exist is not guaranteed to be among the input, and often, it is not.
The alpha-wedge depth of a point with respect to a point set is a natural generalization of halfspace depth that replaces halfspaces with wedges (cones or cocones) of angle alpha.
We introduce the notion of a centervertex, a point with depth at least n/(d+1) among the set S.
We prove that for any finite subset S of R^d, a centervertex exists.
We also present a simple algorithm for computing an approximate centervertex.
@inproceedings{miller09centervertex,
Title = {The Centervertex Theorem for Wedges},
Author = {Gary L. Miller and Todd Phillips and Donald Sheehy},
Booktitle = {CCCG: Canadian Conference in Computational Geometry},
Year = {2009}}
-
Approximate Center Points with Proofs
Gary L. Miller,
Donald R. Sheehy,
SOCG: ACM Symposium on Computational Geometry
2009
We present the Iterated-Tverberg algorithm, the first deterministic algorithm for computing an approximate centerpoint
of a set $S\in R^d$ with running time sub-exponential in $d$.
The algorithm is a derandomization of the Iterated-Radon algorithm of Clarkson et al and is guaranteed to terminate with
an $O(1/d^2)$-center. Moreover, it returns a polynomial-time checkable proof of the approximation guarantee, despite
the coNP-Completenes of testing centerpoints in general.
We also explore the use of higher order Tverberg partitions to improve the runtime of the deterministic algorithm and
improve the approximation guarantee for the randomized algorithm. In particular, we show how to improve the $O(1/d^2)$-
center of the Iterated-Radon algorithm to $O(1/d^{\frac{r}{r-1}})$ for a cost of $O((rd)^{d})$ in time for any integer
$r$.
@inproceedings{miller09approximate,
Title = {Approximate Center Points with Proofs},
Author = {Gary L. Miller and Donald Sheehy},
Booktitle = {SOCG: Proceedings of the 25th ACM Symposium on Computational Geometry},
Year = {2009}}
-
Size Complexity of Volume Meshes vs. Surface Meshes
Benoit Hudson,
Gary L. Miller,
Todd Phillips,
Donald R. Sheehy,
SODA: ACM-SIAM Symposium on Discrete Algorithms
2009
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 may be uniformly spaced or
highly graded, and may have fine resolution due to extrinsic mesh size concerns.
When we desire that such a volume mesh have good aspect ratio, we require that
some space-filling {\it scaffold} vertices be
inserted off the surface. We analyze the number of scaffold vertices
in a setting that encompasses many existing volume meshing algorithms.
We show that under simple preconditions, the number of scaffold
vertices will be linear in the number of surface vertices.
@inproceedings{hudson09size,
Author = {Beno\^{\i}t Hudson and Gary L. Miller and Todd Phillips and Donald Sheehy},
Booktitle = {SODA: ACM-SIAM Symposium on Discrete Algorithms},
Title = {Size Complexity of Volume Meshes vs. Surface Meshes},
Year = {2009}}
-
Shape Deformation in Continuous Map Generalization
Jeff Danciger,
Satyan L. Devadoss,
John Mugno,
Donald R. Sheehy,
Rachel Ward,
GeoInformatica
13
203--221
2009
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 homotopic
deformation. We ask the regions to preserve topology, area-ratios, and relative position as they change over
time. A solution is presented using differential methods and computational geometric techniques. Most
notably, an application of this method is used to provide an algorithm to obtain cartograms.
@article{danciger09shape,
Author = {Jeff Danciger and Satyan Devadoss and John Mugno and Donald Sheehy and Rachel Ward},
Journal = {GeoInformatica},
Number = {2},
Pages = {203--221},
Title = {Shape Deformation in Continuous Map Generalization},
Volume = {13},
Year = {2009}}
2008
-
Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors
Jonathan Derryberry,
Daniel D. Sleator,
Donald R. Sheehy,
Maverick Woo,
CCCG: The Canadian Conference in Computational Geometry
2008
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 $L_t$-norm approximation ratio is $O(d^{1 + 1/t})$, and the running time
for a query $q$ is $O(d^2 \lg \delta(p, q))$, where $p$ is the result of the
preceding query and $\delta(p, q)$ is the number of input points in a
suitably-sized box containing $p$ and $q$.
Our data structure has $O(d n)$ size and requires $O(d^2 n \lg n)$
preprocessing time, where $n$ is the number of points in the data structure.
The size of the bounding box for $\delta$ depends on $d$, and our results
rely on the Random Access Machine (RAM) model with word size $\Theta(\lg
n)$.
@inproceedings{derryberry08achieving,
Author = {John Derryberry and Daniel D. Sleator and Donald Sheehy and Maverick Woo},
Booktitle = {CCCG: Canadian Conference in Computational Geometry},
Title = {Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors},
Year = {2008}}
-
Linear-size meshes
Gary L. Miller,
Todd Phillips,
Donald R. Sheehy,
CCCG: The Canadian Conference in Computational Geometry
2008
Most modern meshing algorithms produce asymptotically optimal size output.
However, the size of the optimal mesh may not be bounded by any function of $n$.
In this paper, we introduce \emph{well-paced} point sets and prove that these will
produce linear size outputs when meshed with any ``size-optimal'' meshing algorithm.
This work generalizes all previous work on the linear cost of balancing quadtrees.
We also present an algorithm that uses well-paced points to produce a linear size
Delaunay mesh of a point set in $R^d$.
@inproceedings{miller08linear,
Author = {Gary L. Miller and Todd Phillips and Donald Sheehy},
Booktitle = {CCCG: Canadian Conference in Computational Geometry},
Title = {Linear-size meshes},
Year = {2008}}
-
Fast sizing calculations for meshing
Gary L. Miller,
Todd Phillips,
Donald R. Sheehy,
The Fall Workshop in in Computational Geometry
2008
Not availiable
@inproceedings{miller08fast,
Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
Booktitle = {The Fall Workshop in Computational Geometry},
Title = {Fast sizing calculations for meshing},
Year = {2008}}
-
Cone Depth and the Center Vertex Theorem
Gary L. Miller,
Todd Phillips,
Donald R. Sheehy,
The Fall Workshop in in Computational Geometry
2008
Not availiable
@inproceedings{miller08cone,
Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
Booktitle = {The Fall Workshop in Computational Geometry},
Title = {Cone Depth and the Center Vertex Theorem},
Year = {2008}}
2007
-
Size Competitive Meshing without Large Angles
Gary L. Miller,
Todd Phillips,
Donald R. Sheehy,
ICALP: 34th International Colloquium on Automata, Languages and Programming
2007
We present a new meshing algorithm for the plane, Overlay Stitch Meshing (OSM),
accepting as input an arbitrary Planar Straight Line Graph and producing a
triangulation with all angles smaller than $170^\circ$.
The output triangulation has competitive size
with any optimal size mesh having equally bounded largest angle.
The competitive ratio is $O(\log(L/s))$ where $L$ and $s$ are respectively the largest and smallest features in the
input. OSM runs in $O(n \log (L/s) + m)$ time/work
where $n$ is the input size and $m$ is the output size.
The algorithm first uses Sparse Voronoi Refinement to compute
a quality overlay mesh of the input points alone.
This triangulation is then combined with the input edges to give the final mesh.
@inproceedings{miller07size,
Author = {Gary L. Miller and Todd Phillips and Donald Sheehy},
Booktitle = {34th International Colloquium on Automata, Languages and Programming},
Title = {Size Competitive Meshing without Large Angles},
Year = {2007}}
2006
-
Compatible Triangulations and Point Partitions by Series Triangular Graphs
Jeff Danciger,
Satyan L. Devadoss,
Donald R. Sheehy,
Computational Geometry: Theory and Applications
34
195--202
2006
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 obtain compatible triangulations of point sets. The problem is
generalized to finding compatible triangulations for more than two point sets and we show
that such triangulations can be constructed with only a linear number of Steiner points added
to each point set. Moreover, the compatible triangulations constructed by these methods
are regular triangulations.
@article{danciger06compatible,
Author = {Jeff Danciger and Satyan Devadoss and Donald Sheehy},
Journal = {Computational Geometry: Theory and Applications},
Pages = {195--202},
Title = {Compatible Triangulations and Point Partitions by Series Triangular Graphs},
Volume = {34},
Year = {2006}}
2005
-
The Complexity of Domino Tiling Problems
Donald R. Sheehy,
Undergraduate Independent Research
2005
