Дэвид Эппштейн. Публикации. Часть E-L

Edge insertion for optimal triangulation

@techreport{BerEdeEpp-TR-92,
title = {{Edge insertion for optimal triangulation}},
author = {Marshall Wayne Bern and Herbert Edelsbrunner and David Eppstein
and Scott A. Mitchell and Tiow-Seng Tan},
institution = {Univ. of Illinois, Urbana-Champaign, Dept. of Computer Science},
number = {UILU-ENG-92-1702},
year = {1992}}

@inproceedings{BerEdeEpp-LATIN-92,
title = {{Edge insertion for optimal triangulation}},
author = {Marshall Wayne Bern and Herbert Edelsbrunner and David Eppstein
and Scott A. Mitchell and Tiow-Seng Tan},
booktitle = {Proc. 1st Latin American Symp. Theoretical Informatics (LATIN
1992)},
number = {583},
editor = {Imre Simon},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
pages = {46--60},
month = {April},
year = {1992}}

@article{BerEdeEpp-DCG-93,
title = {{Edge insertion for optimal triangulation}},
author = {Marshall Wayne Bern and Herbert Edelsbrunner and David Eppstein
and Scott A. Mitchell and Tiow-Seng Tan},
journal = {Discrete {\&} Computational Geometry},
volume = {10},
number = {1},
pages = {47--65},
year = {1993},
url = {http://www.iscs.nus.sg/~tants/Paper/eis.ps.gz},
review = {MR-94i:68279}}

@article{MR-94i:68279,
reviews = {BerEdeEpp-DCG-93},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Edge insertion for optimal triangulation}},
author = {Michael S. Martin},
number = {94i:68279},
year = {1994}}

Efficient algorithms for sequence analysis

@inproceedings{EppGalGia-IAWS-91,
title = {{Efficient algorithms for sequence analysis}},
author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
F. Italiano},
booktitle = {Int. Advanced Worksh. on Sequences, Positano},
year = {1991},
url = {http://www.ics.uci.edu/~eppstein/pubs/EppGalGia-IAWS-91.pdf}}

@incollection{EppGalGia-S2-93,
title = {{Efficient algorithms for sequence analysis}},
author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
F. Italiano},
booktitle = {Sequences II: Communication, Security, and Computer Science},
publisher = {Springer-Verlag},
editor = {Renato M. Capocelli and De Santis, Alfredo and Ugo Vaccaro},
pages = {225--244},
year = {1993},
note = {From Int. Advanced Worksh. Sequences, Positano, Italy, June 1991}}

Efficient algorithms for sequence analysis with concave and convex gap costs

@phdthesis{Epp-PhD-89,
title = {{Efficient algorithms for sequence analysis with concave and convex
gap costs}},
author = {David Eppstein},
address = {New York, NY, 10027, USA},
school = {Columbia Univ., Computer Science Dept.},
year = {1989},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-PhD-89.pdf}}

Efficient algorithms with applications to molecular biology

@incollection{EppGalGia-Seq-90,
title = {{Efficient algorithms with applications to molecular biology}},
author = {David Eppstein and Zvi Galil and Raffaele Giancarlo},
booktitle = {Sequences: Combinatorics, Compression, Security, Transmission},
publisher = {Springer-Verlag},
editor = {Renato M. Capocelli},
pages = {59--74},
year = {1990},
note = {From Int. Advanced Worksh. Sequences, Positano, Italy, June 1988},
review = {MR-91a:68125}}

@article{MR-91a:68125,
reviews = {EppGalGia-Seq-90},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Efficient algorithms with applications to molecular biology}},
author = {Ralph G. Stanton},
number = {91a:68125},
year = {1991}}

Efficient sequential and parallel algorithms for computing recovery points in trees and paths

@techreport{ChrEppIta-TR-91,
title = {{Efficient sequential and parallel algorithms for computing recovery
points in trees and paths}},
author = {Marek Chrobak and David Eppstein and Giuseppe F. Italiano and
Moti Yung},
type = {ALCOM Report},
institution = {Univ. di Roma ``La Sapienza'', Dip. di Informatica e Sistemistica},
number = {91-74},
year = {1991}}

@inproceedings{ChrEppIta-SODA-91,
title = {{Efficient sequential and parallel algorithms for computing recovery
points in trees and paths}},
author = {Marek Chrobak and David Eppstein and Giuseppe F. Italiano and
Moti Yung},
booktitle = {Proc. 2nd Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {158--167},
month = {January},
year = {1991}}

Emerging challenges in computational topology

@misc{cs.CG/9909001,
title = {{Emerging challenges in computational topology}},
author = {Marshall Wayne Bern and David Eppstein and others},
eprint = {cs.CG/9909001},
howpublished = {ACM Computing Research Repository},
month = {September},
year = {1999}}

Equipartitions of graphs

@article{EppFeiLi-DM-91,
title = {{Equipartitions of graphs}},
author = {David Eppstein and Joan Feigenbaum and Chung-Lun Li},
journal = {Discrete Mathematics},
volume = {91},
number = {3},
pages = {239--248},
year = {1991},
url = {http://dx.doi.org/10.1016/0012-365X(90)90233-8},
review = {MR-92k:05125}}

@article{MR-92k:05125,
reviews = {EppFeiLi-DM-91},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Equipartitions of graphs}},
author = {Marek E. Kubale},
number = {92k:05125},
year = {1992}}

Fast approximation of centrality

@misc{cs.DS/0009005,
title = {{Fast approximation of centrality}},
author = {David Eppstein and Joseph Yannkae Wang},
eprint = {cs.DS/0009005},
howpublished = {ACM Computing Research Repository},
month = {September},
year = {2000}}

@inproceedings{EppWan-SODA-01,
title = {{Fast approximation of centrality}},
author = {David Eppstein and Joseph Yannkae Wang},
eprint = {cs.DS/0009005},
booktitle = {Proc. 12th Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {228--229},
month = {January},
year = {2001}}

Fast hierarchical clustering and other applications of dynamic closest pairs

@inproceedings{Epp-SODA-98,
title = {{Fast hierarchical clustering and other applications of dynamic
closest pairs}},
author = {David Eppstein},
eprint = {cs.DS/9912014},
booktitle = {Proc. 9th Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {619--628},
month = {January},
year = {1998},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-SODA-98.pdf}}

@misc{cs.DS/9912014,
title = {{Fast hierarchical clustering and other applications of dynamic
closest pairs}},
author = {David Eppstein},
eprint = {cs.DS/9912014},
howpublished = {ACM Computing Research Repository},
month = {December},
year = {1999}}

@article{Epp-JEA-00,
title = {{Fast hierarchical clustering and other applications of dynamic
closest pairs}},
author = {David Eppstein},
eprint = {cs.DS/9912014},
journal = {J. Experimental Algorithmics},
publisher = {ACM},
volume = {5},
number = {1},
pages = {1--23},
month = {June},
year = {2000},
url = {http://www.jea.acm.org/2000/EppsteinDynamic/}}

Fast optimal parallel algorithms for maximal matching in sparse graphs

@techreport{AsuDilEpp-TR-92,
title = {{Fast optimal parallel algorithms for maximal matching in sparse
graphs}},
author = {Hari Asuri and Michael B. Dillencourt and David Eppstein and
George S. Lueker and Mariko Molodowitch},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {92-01},
year = {1992}}

Faster circle packing with application to nonobtuse triangulation

@techreport{Epp-TR-94-33,
title = {{Faster circle packing with application to nonobtuse triangulation}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {94-33},
year = {1994},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-33.pdf}}

@article{Epp-IJCGA-97,
title = {{Faster circle packing with application to nonobtuse triangulation}},
author = {David Eppstein},
journal = {Int. J. Computational Geometry {\&} Applications},
volume = {7},
number = {5},
pages = {485--491},
month = {October},
year = {1997},
review = {MR-99d:52018}}

@article{MR-99d:52018,
reviews = {Epp-IJCGA-97},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Faster circle packing with application to nonobtuse triangulation}},
author = {Frederic Matheus},
number = {99d:52018},
year = {1999},
text = {Numerical computations regarding the discretization of Dirichlet
problems in polygonal domains need to generate triangulations with right
or acute angles. The author considers here a recent work of Bern, Mitchell
and Ruppert which uses circle packings to generate such meshes and speed
up a key step of their method in which circles are packed into a non-simply
connected polygonal region to connect its boundary components.

In the work of Bern et al., this step was computed in $O(n\log\sp {2}n)$
time. The new method presented here leads to an overall speedup of a
logarithmic factor, which makes the whole algorithm work in total time
$O(n\log n)$.

This method for connecting the boundary components of a polygon relies
on a combination of several known techniques such as: Voronoi diagrams,
minimum spanning trees, intersection graphs, neighborhood system algorithms
of Eppstein, Miller and Teng, and dynamic tree techniques of Sleator
and Tarjan.}}

Faster construction of planar two-centers

@techreport{Epp-TR-96-12,
title = {{Faster construction of planar two-centers}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {96-12},
year = {1996},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-12.pdf}}

@inproceedings{Epp-SODA-97,
title = {{Faster construction of planar two-centers}},
author = {David Eppstein},
booktitle = {Proc. 8th Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {131--138},
month = {January},
year = {1997},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-SODA-97.pdf}}

Faster geometric $k$-point MST approximation

@techreport{Epp-TR-95-13,
title = {{Faster geometric $k$-point MST approximation}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {95-13},
year = {1995},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-13.pdf}}

@article{Epp-CGTA-97,
title = {{Faster geometric $k$-point MST approximation}},
author = {David Eppstein},
journal = {Computational Geometry Theory {\&} Applications},
volume = {8},
pages = {231--240},
month = {October},
year = {1997},
review = {MR-98d:68199}}

@article{MR-98d:68199,
reviews = {Epp-CGTA-97},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Faster geometric $k$-point MST approximation}},
number = {98d:68199},
year = {1998}}

Fat 4-polytopes and fatter 3-spheres

@misc{math.CO/0204007,
title = {{Fat 4-polytopes and fatter 3-spheres}},
author = {David Eppstein and Greg Kuperberg and G{\"u}nter M. Ziegler},
eprint = {math.CO/0204007},
howpublished = {arXiv.org e-Print archive},
month = {April},
year = {2002}}

@incollection{EppKupZie-WK-03,
title = {{Fat 4-polytopes and fatter 3-spheres}},
author = {David Eppstein and Greg Kuperberg and G{\"u}nter M. Ziegler},
eprint = {math.CO/0204007},
booktitle = {Discrete Geometry: In honor of W. Kuperberg's 60th birthday},
number = {253},
editor = {Andras Bezdek},
series = {Pure and Applied Mathematics},
publisher = {Marcel Dekker},
pages = {239--265},
year = {2003},
review = {MR-2034720}}

@article{MR-2034720,
reviews = {EppKupZie-WK-03},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Fat 4-polytopes and fatter 3-spheres}},
number = {2034720},
year = {2004}}

Finding common ancestors and disjoint paths in DAGs

@techreport{Epp-TR-95-52,
title = {{Finding common ancestors and disjoint paths in DAGs}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {95-52},
year = {1995},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-52.pdf}}

Finding minimum area $k$-gons

@article{EppOveRot-DCG-92,
title = {{Finding minimum area $k$-gons}},
author = {David Eppstein and Mark Overmars and G{\"u}nter Rote and Gerhard
J. Woeginger},
journal = {Discrete {\&} Computational Geometry},
volume = {7},
number = {1},
pages = {45--58},
year = {1992},
url = {http://www.ics.uci.edu/~eppstein/pubs/EppOveRot-DCG-92.pdf},
review = {MR-92k:52026}}

@article{MR-92k:52026,
reviews = {EppOveRot-DCG-92},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Finding minimum area $k$-gons}},
author = {Ivan Stojmenov{\'\i}c},
number = {92k:52026},
year = {1992}}

Finding the $k$ shortest paths

@techreport{Epp-TR-94-26,
title = {{Finding the $k$ shortest paths}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {94-26},
year = {1994},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-26.pdf}}

@inproceedings{Epp-FOCS-94,
title = {{Finding the $k$ shortest paths}},
author = {David Eppstein},
booktitle = {Proc. 35th Symp. Foundations of Computer Science},
publisher = {IEEE},
pages = {154--165},
month = {November},
year = {1994}}

@article{Epp-SJC-98,
title = {{Finding the $k$ shortest paths}},
author = {David Eppstein},
journal = {SIAM J. Computing},
publisher = {SIAM},
volume = {28},
number = {2},
pages = {652--673},
year = {1998},
url = {http://dx.doi.org/10.1137/S0097539795290477},
review = {MR-99h:05073}}

@article{MR-99h:05073,
reviews = {Epp-SJC-98},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Finding the $k$ shortest paths}},
author = {Koduvayur R. Parthasarathy},
number = {99h:05073},
year = {1999},
text = {The $k$-shortest-paths problem is to list the $k$ paths from a
specified source $s$ to a specified destination $t$ in a digraph, with
minimum total length. The author considers digraphs admitting self-loops,
multiple edges and cycles without negative lengths, and the paths are
not necessarily simple. Using an implicit representation of the paths,
the author presents, in detail, an algorithm with time complexity $O(m+n\log
n+k)$ where $n$ and $m$ are the number of vertices and the number of
edges of the digraph. This also leads to an algorithm of complexity $O(m+n\log
n+kn)$ for the $k$-shortest-paths problem from a given source $s$ to
all other vertices of the graph.

To get the implicit representation, one starts with a single-destination
$(t)$ shortest path tree $T$ of the given digraph $G$ with source $s$
and destination $t$ and produces a heap $H\sb G(v)$ at each vertex $v$
leading to a directed acyclic graph $D(G)$ and through that to a path
graph $P(G)$, with the property that there is a one-to-one "length-preserving"
correspondence between $s$-$t$ paths in $G$ and paths starting from the
root $r$ in $P(G)$ and finally to a 4-heap $H(G)$ whose nodes correspond
to the $s$-$t$ paths of $G$. After developing a basic algorithm, improvements
are introduced in the heap construction to attain the above complexity.


The improvements in time complexity achieved through this algorithm when
used for the dynamic programming applications to the following optimization
problems are discussed at some length: the knapsack problem, sequence
alignment, inscribed polygons, and genealogical relations. Three open
problems are suggested.}}

Finding the $k$ smallest spanning trees

@inproceedings{Epp-SWAT-90,
title = {{Finding the $k$ smallest spanning trees}},
author = {David Eppstein},
booktitle = {Proc. 2nd Scandinavian Worksh. Algorithm Theory (SWAT 1990)},
number = {447},
editor = {John Russell Gilbert and Rolf G. Karlsson},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
pages = {38--47},
month = {July},
year = {1990}}

@article{Epp-BIT-92,
title = {{Finding the $k$ smallest spanning trees}},
author = {David Eppstein},
journal = {BIT},
volume = {32},
number = {2},
pages = {237--248},
year = {1992},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-BIT-92.pdf},
note = {Special issue for 2nd SWAT},
review = {MR-94e:05082}}

@article{MR-94e:05082,
reviews = {Epp-BIT-92},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Finding the $k$ smallest spanning trees}},
author = {Maciej M. Sys{\l}o},
number = {94e:05082},
year = {1994}}

Flipping cubical meshes

@misc{cs.CG/0108020,
title = {{Flipping cubical meshes}},
author = {Marshall Wayne Bern and David Eppstein and Jeffrey Gordon Erickson},
eprint = {cs.CG/0108020},
howpublished = {ACM Computing Research Repository},
month = {August},
year = {2001}}

@article{BerEppEri-EwC-02,
title = {{Flipping cubical meshes}},
author = {Marshall Wayne Bern and David Eppstein and Jeffrey Gordon Erickson},
eprint = {cs.CG/0108020},
journal = {Engineering with Computers},
volume = {18},
number = {3},
pages = {173--187},
month = {October},
year = {2002}}

Flipping cubical meshes{}

@inproceedings{BerEpp-IMR-01,
title = {{Flipping cubical meshes{}}},
author = {Marshall Wayne Bern and David Eppstein},
booktitle = {Proc. 10th Int. Meshing Roundtable},
publisher = {Sandia Nat. Lab.},
pages = {19--29},
month = {October},
year = {2001}}

Geometric lower bounds for parametric matroid optimization

@techreport{Epp-TR-95-11,
title = {{Geometric lower bounds for parametric matroid optimization}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {95-11},
year = {1995}}

@inproceedings{Epp-STOC-95,
title = {{Geometric lower bounds for parametric matroid optimization}},
author = {David Eppstein},
booktitle = {Proc. 27th Symp. Theory of Computing},
publisher = {ACM},
pages = {662--671},
month = {June},
year = {1995},
url = {http://www.acm.org/pubs/citations/proceedings/stoc/225058/p662-eppstein}}

@article{Epp-DCG-98,
title = {{Geometric lower bounds for parametric matroid optimization}},
author = {David Eppstein},
journal = {Discrete {\&} Computational Geometry},
volume = {20},
pages = {463--476},
year = {1998},
url = {http://link.springer.de/link/service/journals/00454/bibs/20n4p463.html},
review = {MR-99h:90082}}

@article{MR-99h:90082,
reviews = {Epp-DCG-98},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Geometric lower bounds for parametric matroid optimization}},
author = {De Loera, Jes{\'u}s A.},
number = {99h:90082},
year = {1999},
text = {The author deduces some results on matroid optimization by using
geometric techniques. For example, the following lower bounds are proved,
using their relation to polygon arrangements and lower envelopes of line
segments: (1) There can be $\Omega (nr\sp {1/3})$ different minimum weight
bases in a matroid with $n$ elements, rank $r$ and element weights linearly
varying with time. (2) There can be $\Omega (m \alpha(n))$ different
minimum spanning trees in a graph with $m$ edges, $n$ vertices, and edge
weights linearly varying with time, where $\alpha(n)$ denotes the inverse
Ackermann function.

Recently, T. K. Dey [Discrete Comput. Geom. 19 (1998), no. 3, Special
Issue, 373--382; MR 98k:52018] obtained an $O(nr\sp {1/3})$ upper bound
on the number of base changes in a parametric matroid optimization problem,
that matches the lower bound presented in this article.}}

Geometric thickness of complete graphs

@inproceedings{DilEppHir-GD-98,
title = {{Geometric thickness of complete graphs}},
author = {Michael B. Dillencourt and David Eppstein and Daniel S. Hirschberg},
eprint = {math.CO/9910185},
booktitle = {Proc. 6th Int. Symp. Graph Drawing (GD 1998)},
number = {1547},
editor = {Sue Whitesides},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
pages = {102--110},
month = {August},
year = {1998},
review = {MR-2000g-68118}}

@article{MR-2000g-68118,
reviews = {DilEppHir-GD-98},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Geometric thickness of complete graphs}},
volume = {2000g},
number = {68118},
year = {2000}}

@misc{math.CO/9910185,
title = {{Geometric thickness of complete graphs}},
author = {Michael B. Dillencourt and David Eppstein and Daniel S. Hirschberg},
eprint = {math.CO/9910185},
howpublished = {arXiv.org e-Print archive},
month = {October},
year = {1999}}

@article{DilEppHir-JGAA-00,
title = {{Geometric thickness of complete graphs}},
author = {Michael B. Dillencourt and David Eppstein and Daniel S. Hirschberg},
eprint = {math.CO/9910185},
journal = {J. Graph Algorithms {\&} Applications},
volume = {4},
number = {3},
pages = {5--17},
year = {2000},
note = {Special issue for Graph Drawing '98},
review = {MR-2004f:05044}}

@article{MR-2004f:05044,
reviews = {DilEppHir-JGAA-00},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Geometric thickness of complete graphs}},
number = {2004f:05044},
year = {2004}}

Global optimization of mesh quality

@misc{Epp-IMR-01,
title = {{Global optimization of mesh quality}},
author = {David Eppstein},
howpublished = {Tutorial at 10th Int. Meshing Roundtable},
year = {2001},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-IMR-01.pdf}}

Guest editor's forward to special issue for ACM Symp. on Computational Geometry

@article{Epp-DCG-03,
title = {{Guest editor's forward to special issue for ACM Symp. on Computational
Geometry}},
author = {David Eppstein},
journal = {Discrete {\&} Computational Geometry},
volume = {30},
number = {1},
pages = {1--2},
month = {July},
year = {2003}}

Guest editor's forward to special issue of papers from the 34th Annual Symposium on Foundations of Computer Science

@article{Epp-JCSS-97,
title = {{Guest editor's forward to special issue of papers from the 34th
Annual Symposium on Foundations of Computer Science}},
author = {David Eppstein},
journal = {J. Computer {\&} Systems Sciences},
volume = {54},
number = {2},
pages = {263},
month = {April},
year = {1997}}

Guest editor's forword to special issue on dynamic graph algorithms

@article{Epp-Algo-98,
title = {{Guest editor's forword to special issue on dynamic graph algorithms}},
author = {David Eppstein},
journal = {Algorithmica},
volume = {22},
number = {3},
pages = {233--234},
month = {November},
year = {1998}}

Hinged dissections of polyominoes and polyforms

@article{DemDemEpp-CGTA-?,
title = {{Hinged dissections of polyominoes and polyforms}},
author = {Erik D. Demaine and Martin L. Demaine and David Eppstein and
Erich Friedman},
eprint = {cs.CG/9907018},
journal = {Computational Geometry Theory {\&} Applications},
note = {To appear}}

@misc{cs.CG/9907018,
title = {{Hinged dissections of polyominoes and polyforms}},
author = {Erik D. Demaine and Martin L. Demaine and David Eppstein and
Erich Friedman},
eprint = {cs.CG/9907018},
howpublished = {ACM Computing Research Repository},
month = {July},
year = {1999}}

@inproceedings{DemDemEpp-CCCG-99,
title = {{Hinged dissections of polyominoes and polyforms}},
author = {Erik D. Demaine and Martin L. Demaine and David Eppstein and
Erich Friedman},
eprint = {cs.CG/9907018},
booktitle = {Proc. 11th Canad. Conf. Computational Geometry},
month = {August},
year = {1999},
url = {http://www.cs.ubc.ca/conferences/CCCG/elec_proc/fp37.pdf}}

Hinged kite mirror dissection

@misc{cs.CG/0106032,
title = {{Hinged kite mirror dissection}},
author = {David Eppstein},
eprint = {cs.CG/0106032},
howpublished = {ACM Computing Research Repository},
month = {June},
year = {2001}}

Horizon theorems for lines and polygons

@incollection{BerEppPla-DCG-91,
title = {{Horizon theorems for lines and polygons}},
author = {Marshall Wayne Bern and David Eppstein and Paul E. Plassman and
Frances F. Yao},
booktitle = {Discrete and Computational Geometry: Papers from the DIMACS
Special Year},
number = {6},
editor = {Jacob E. Goodman and Richard Pollack and William Steiger},
series = {DIMACS Ser. Discrete Math. and Theoretical Computer Science},
publisher = {Amer. Math. Soc.},
pages = {45--66},
year = {1991},
review = {MR-92j:52023}}

@article{MR-92j:52023,
reviews = {BerEppPla-DCG-91},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Horizon theorems for lines and polygons}},
author = {Robert Connelly},
number = {92j:52023},
year = {1992}}

Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction

@misc{cs.DS/0009006,
title = {{Improved algorithms for 3-coloring, 3-edge-coloring, and constraint
satisfaction}},
author = {David Eppstein},
eprint = {cs.DS/0009006},
howpublished = {ACM Computing Research Repository},
month = {September},
year = {2000}}

@inproceedings{Epp-SODA-01,
title = {{Improved algorithms for 3-coloring, 3-edge-coloring, and constraint
satisfaction}},
author = {David Eppstein},
eprint = {cs.DS/0009006},
booktitle = {Proc. 12th Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {329--337},
month = {January},
year = {2001}}

Improved bounds for intersecting triangles and halving planes

@techreport{Epp-TR-91-60,
title = {{Improved bounds for intersecting triangles and halving planes}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {91-60},
year = {1991},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-91-60.pdf}}

@article{Epp-JCT-93,
title = {{Improved bounds for intersecting triangles and halving planes}},
author = {David Eppstein},
journal = {J. Combinatorial Theory, Series A},
volume = {62},
pages = {176--182},
year = {1993},
review = {MR-94f:52006}}

@article{MR-94f:52006,
reviews = {Epp-JCT-93},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Improved bounds for intersecting triangles and halving planes}},
author = {Leroy M. Kelly},
number = {94f:52006},
year = {1994}}

Improved combinatorial group testing for real-world problem sizes

@inproceedings{EppGooHir-WADS-05,
title = {{Improved combinatorial group testing for real-world problem sizes}},
author = {David Eppstein and Michael T. Goodrich and Daniel S. Hirschberg},
eprint = {cs.DS/0505048},
booktitle = {Proc. 9th Worksh. Algorithms and Data Structures (WADS 2005)},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
note = {To appear.}}

@misc{cs.DS/0505048,
title = {{Improved combinatorial group testing for real-world problem sizes}},
author = {David Eppstein and Michael T. Goodrich and Daniel S. Hirschberg},
eprint = {cs.DS/0505048},
howpublished = {ACM Computing Research Repository},
month = {May},
year = {2005}}

Improved sparsification

@techreport{EppGalIta-TR-93,
title = {{Improved sparsification}},
author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {93-20},
year = {1993},
url = {http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf}}

Incremental and decremental maintenance of planar width

@misc{cs.CG/9809038,
title = {{Incremental and decremental maintenance of planar width}},
author = {David Eppstein},
eprint = {cs.CG/9809038},
howpublished = {ACM Computing Research Repository},
month = {September},
year = {1998}}

@inproceedings{Epp-SODA-99,
title = {{Incremental and decremental maintenance of planar width}},
author = {David Eppstein},
eprint = {cs.CG/9809038},
booktitle = {Proc. 10th Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {S899--S900},
month = {January},
year = {1999}}

@article{Epp-Algs-00,
title = {{Incremental and decremental maintenance of planar width}},
author = {David Eppstein},
eprint = {cs.CG/9809038},
journal = {J. Algorithms},
volume = {37},
number = {2},
pages = {570--577},
month = {November},
year = {2000},
url = {http://dx.doi.org/10.1006/jagm.2000.1107},
review = {MR-2001g-68095}}

@article{MR-2001g-68095,
reviews = {Epp-Algs-00},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Incremental and decremental maintenance of planar width}},
volume = {2001g},
number = {68095},
year = {2001}}

Internet packet filter management and rectangle geometry

@misc{cs.CG/0010018,
title = {{Internet packet filter management and rectangle geometry}},
author = {David Eppstein and Shanmugauelayut Muthukrishnan},
eprint = {cs.CG/0010018},
howpublished = {ACM Computing Research Repository},
month = {October},
year = {2000}}

@inproceedings{EppMut-SODA-01,
title = {{Internet packet filter management and rectangle geometry}},
author = {David Eppstein and Shanmugauelayut Muthukrishnan},
eprint = {cs.CG/0010018},
booktitle = {Proc. 12th Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {827--835},
month = {January},
year = {2001}}

Iterated nearest neighbors and finding minimal polytopes

@techreport{EppEri-TR-92-71,
title = {{Iterated nearest neighbors and finding minimal polytopes}},
author = {David Eppstein and Jeffrey Gordon Erickson},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {92-71},
year = {1992}}

@inproceedings{EppEri-SODA-93,
title = {{Iterated nearest neighbors and finding minimal polytopes}},
author = {David Eppstein and Jeffrey Gordon Erickson},
booktitle = {Proc. 4th Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {64--73},
month = {January},
year = {1993},
review = {MR-94c:68197}}

@article{MR-94c:68197,
reviews = {EppEri-SODA-93},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Iterated nearest neighbors and finding minimal polytopes}},
number = {94c:68197},
year = {1994}}

@article{EppEri-DCG-94,
title = {{Iterated nearest neighbors and finding minimal polytopes}},
author = {David Eppstein and Jeffrey Gordon Erickson},
journal = {Discrete {\&} Computational Geometry},
volume = {11},
number = {3},
pages = {321--350},
month = {April},
year = {1994},
url = {http://www.cs.duke.edu/~jeffe/pubs/small.html},
review = {MR-95a:68100}}

@article{MR-95a:68100,
reviews = {EppEri-DCG-94},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Iterated nearest neighbors and finding minimal polytopes}},
author = {Mark E. Hartmann},
number = {95a:68100},
year = {1995}}

Lazy algorithms for dynamic closest pair with arbitrary distance measures

@techreport{CarEpp-TR-03,
title = {{Lazy algorithms for dynamic closest pair with arbitrary distance
measures}},
author = {Jean Cardinal and David Eppstein},
institution = {Univ. Libre de Bruxelles, Computer Science Dept.},
number = {502},
year = {2003}}

@inproceedings{CarEpp-ALENEX-04,
title = {{Lazy algorithms for dynamic closest pair with arbitrary distance
measures}},
author = {Jean Cardinal and David Eppstein},
booktitle = {Joint Proc. Worksh. Algorithm Engineering and Experiments
(ALENEX) and Worksh. Analytic Algorithmics and Combinatorics (ANALCO)},
publisher = {ACM and SIAM},
pages = {112--119},
year = {2004}}

Linear complexity hexahedral mesh generation

@techreport{Epp-TR-95-51,
title = {{Linear complexity hexahedral mesh generation}},
author = {David Eppstein},
eprint = {cs.CG/9809109},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {95-51},
year = {1995},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-51.pdf}}

@inproceedings{Epp-SCG-96,
title = {{Linear complexity hexahedral mesh generation}},
author = {David Eppstein},
eprint = {cs.CG/9809109},
booktitle = {Proc. 12th Symp. Computational Geometry},
publisher = {ACM},
pages = {58--67},
month = {May},
year = {1996},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-SCG-96.pdf}}

@misc{cs.CG/9809109,
title = {{Linear complexity hexahedral mesh generation}},
author = {David Eppstein},
eprint = {cs.CG/9809109},
howpublished = {ACM Computing Research Repository},
month = {September},
year = {1998}}

@article{Epp-CGTA-99,
title = {{Linear complexity hexahedral mesh generation}},
author = {David Eppstein},
eprint = {cs.CG/9809109},
journal = {Computational Geometry Theory {\&} Applications},
volume = {12},
pages = {3--16},
year = {1999},
note = {Special issue for 12th Symp. Comp. Geom.},
review = {MR-2000a:68153}}

@article{MR-2000a:68153,
reviews = {Epp-CGTA-99},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Linear complexity hexahedral mesh generation}},
author = {de Figueiredo, Luiz Henrique},
number = {2000a:68153},
year = {2000},
text = {One important problem in mesh generation is how to extend a given
mesh on the surface of a solid to its interior. Most results on such
problems, especially theoretical ones, are restricted to the extension
of triangular meshes to tetrahedral meshes. However, in practice, quadrilateral
and hexahedral meshes are often preferred because of their numerical
properties. Few theoretical results are known for this case. For planar
meshes, it has been proved [S. Ramaswami, P. A. Ramos and G. T. Toussaint,
Comput. Geom. 9 (1998), no. 4, 257--276; MR 98k:68169] that a polygon
with $n$ sides can be meshed with convex quadrilaterals if and only if
$n$ is even. Moreover, $O(n)$ Steiner points suffice as the vertices
of the internal mesh, and they can be found efficiently. Thurston and
Mitchell independently proved a similar result for spatial meshes, but
it is restricted to solids whose boundaries are topological spheres.
The resulting internal mesh is only topological, not geometric, in the
sense that the hexahedral elements have curved boundaries and are not
necessarily convex. Moreover, the size of the internal mesh is not linear
in the size of the boundary mesh. In this paper, the author removes this
restriction and proves that any polyhedron which is topologically a sphere
and whose boundary is composed of an even number of quadrilateral faces
can be meshed with a linear number of topological cubes. The author has
made some progress in extending this proof to geometric meshes---only
a finite number of cases are left to be tested, and this could be done
by machine---but, as he points out, this extension would not be directly
practical because the size of the interior mesh may be large, albeit
linear, and its elements will be poorly shaped.}}