72 citations · 218 across the 10 of their papers we have counts for
5 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…
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…