David Eppstein - Publications
ARO-MSI and CGC Workshops in Computational Geometry
- Dynamic geometric optimization.
3rd MSI Worksh. Computational Geometry, 1993, p. 14.
- Choosing subsets with maximum weighted average.
D. Eppstein and
D. S. Hirschberg.
Tech. Rep. 95-12, ICS, UCI, 1995.
5th MSI Worksh. on Computational Geometry, 1995, pp. 7–8.
J. Algorithms 24: 177–193, 1997.
Uses geometric optimization techniques to find, among n weighted values,
the k to drop so as to maximize the weighted average of the remaining values.
The feasibility test for the corresponding decision problem involves
k-sets in a dual line arrangement.
Full paper –
- Quadrilateral meshing by circle packing.
and D. Eppstein.
Worksh. Computational Geometry, Durham, North Carolina, 1997.
6th Int. Meshing Roundtable, Park
City, Utah, 1997, pp. 7–19.
Int. J. Comp. Geom. & Appl. 10 (4): 347–360, 2000.
We use circle-packing methods to generate
quadrilateral meshes for
polygonal domains, with guaranteed bounds both on the quality and the
number of elements. We show that these methods can generate meshes of
In each case the total number of elements is O(n).
The 120-degree bound is optimal; if a simply-connected region has all
angles at least 120 degrees, any mesh of that region has a 120 degree
- The elements form the cells of a Voronoi diagram,
- The elements each have two opposite 90 degree angles,
- All elements are kites, or
- All angles are at most 120 degrees.
- Regression depth and center points.
D. Eppstein, and
Worksh. Computational Geometry, Brown Univ., 1998.
Disc. Comp. Geom. 23 (3): 305–323, 2000.
We show that, for any set of n points in d dimensions, there exists a
regression depth at least ceiling(n/(d+1)). as had
been conjectured by Rousseeuw and Hubert. Dually, for any
arrangement of n hyperplanes in d dimensions there exists a point
that cannot escape to infinity without crossing at least
ceiling(n/(d+1)) hyperplanes. We also apply our approach to
related questions on the existence of partitions of the data into
subsets such that a common plane has nonzero regression depth in
each subset, and to the computational complexity of regression
- Ununfoldable polyhedra.
A. Mantler, and
CS-99-04, Univ. of Waterloo, Dept. of Computer Science, Aug. 1999.
11th Canad. Conf. Comp. Geom., 1999.
Worksh. Computational Geometry, Johns Hopkins Univ., 1999.
Comp. Geom. Theory & Applications (special
issue for 4th CGC Worksh.) 24 (2): 51–62, 2003.
We prove the existence of polyhedra in which all faces are convex,
but which can not be cut along edges and folded flat.
Note variations in different versions: the CCCG one was only Bern,
Demain, Eppstein, and Kuo, and the WCG one had the title "Ununfoldable
polyhedra with triangular faces". The journal version uses the title
"Ununfoldable polyhedra with convex faces" and
the combined results from both conference versions.
publication page –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
from a common source file.