David Eppstein - Publications

Halving lines and k-sets

• Sets of points with many halving lines.
  D. Eppstein.
  Tech. Rep. 92-86, ICS, UCI, 1992.

  I used genetic algorithms to search for small configurations of points bisected by lines in many combinatorially distinct ways.

• Improved bounds for intersecting triangles and halving planes.
  D. Eppstein.
  Tech. Rep. 91-60, ICS, UCI, 1991.
  J. Combinatorial Theory Ser. A 62: 176–182, 1993.

  Reduces the polylogarithmic term in an upper bound for the three-dimensional k-set problem.

  A bug in the proof was corrected by Nivasch and Sharir.

• Geometric lower bounds for parametric matroid optimization.
  D. Eppstein.
  Tech. Rep. 95-11, ICS, UCI, 1995.
  27th ACM Symp. Theory of Computing, Las Vegas, 1995, pp. 662–671.
  Disc. Comp. Geom. 20: 463–476, 1998.

  Considers graphs in which edge weights are linear functions of time. Shows nonlinear lower bounds on the number of different minimum spanning trees appearing over time by translation from geometric problem of lower envelopes of line segments. A matroid generalization has a better lower bound coming from many faces in line arrangements, and the uniform matroid problem is equivalent to the geometric k-set problem.

• 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)

Geometry – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.