72 citations · 218 across the 15 of their papers we have counts for
17 papers · 1 filter
The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data
David Eppstein, Michael T. Goodrich, Jonathan Z. Sun
We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R^2) or the skip octree (for point data in R^d, with constant d>2). Our data s…
The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems
Josiah Carlson, David Eppstein
We consider problems in which we are given a rooted tree as input, and must find a subtree with the same root, optimizing some objective function of the nodes in the subtree. When…
Quasiconvex Programming
David Eppstein
We define quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions.…
Single-Strip Triangulation of Manifolds with Arbitrary Topology
M. Gopi, David Eppstein
Triangle strips have been widely used for efficient rendering. It is NP-complete to test whether a given triangulated model can be represented as a single triangle strip, so many h…
The Geometric Thickness of Low Degree Graphs
Christian A. Duncan, David Eppstein, Stephen G. Kobourov
We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the g…
Tiling space and slabs with acute tetrahedra
David Eppstein, John M. Sullivan, Alper Ungor
We show it is possible to tile three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which al…