% BibTeX database kset.bib
% exported by BibGene 1.0d, Tue, Feb 18, 1997.

% Bibliography on k-sets, parametric matroid optimization, etc
% David Eppstein, UC Irvine, Dept. Information & Computer Science
% http://www.ics.uci.edu/~eppstein/
%
% This file collects papers on subjects related to levels in arrangements
% of curves and surfaces.  This subject has many disguised forms and
% generalizations: In one direction, via projective duality, it leads to
% counting partitions of a point set by lines (so-called k-sets).  In another,
% it is equivalent (via projection) to construction of order-k Voronoi
% diagrams.  And in a third direction, the one I have collected the most
% references on, it leads to problems of parametric optimization (such as
% graph minimum spanning trees with linearly varying edge weights),
% and from there back to other geometry problems including lower
% envelopes and many-face bounds in arrangements; see my paper
% Epp-STOC-95 for an explanation of these connections.


@inproceedings{AgaBerMat-SCG-94,
  title = {{Constructing levels in arrangements and higher order Voronoi diagrams}},
  author = {Pankaj K. Agarwal and Mark de Berg and Ji{\v{r}}{\'\i} Matou{\v{s}}ek and Otfried Schwarzkopf},
  keywords = {levels, order-k voronoi},
  booktitle = {Proc. 10th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {67--75},
  year = {1994}}

@article{AleBoiPre-Algo-90,
  title = {{An optimal algorithm for the boundary of a cell in a union of rays}},
  author = {P. Alevizos and Jean-Daniel Boissonnat and Franco P. Preparata},
  journal = {Algorithmica},
  volume = {5},
  pages = {573--590},
  year = {1990}}

@article{AleBoiPre-Algo-91,
  title = {{An optimal algorithm for the boundary of a cell in a union of rays}},
  author = {P. Alevizos and Jean-Daniel Boissonnat and Franco P. Preparata},
  journal = {Algorithmica},
  volume = {6},
  pages = {292--293},
  year = {1991},
  note = {Corrigendum to \cite{AleBoiPre-Algo-90}}}

@article{AloGyo-JCTA-86,
  title = {{The number of small semispaces of a finite set of points in the plane}},
  author = {Noga Alon and E. Gy{\"o}ri},
  keywords = {k-sets},
  journal = {J. Combinatorial Theory, Ser. A},
  volume = {41},
  pages = {154--157},
  year = {1986}}

@article{AroChaEde-DCG-91,
  title = {{Points and triangles in the plane and halving planes in space}},
  author = {Boris Aronov and Bernard M. Chazelle and Herbert Edelsbrunner and Leonidas J. Guibas and Micha Sharir and R. Wenger},
  keywords = {k-sets},
  journal = {Discrete {\&} Computational Geometry},
  volume = {6},
  pages = {435--442},
  year = {1991}}

@inproceedings{AroChaEde-SCG-90,
  title = {{Points and triangles in the plane and halving planes in space}},
  author = {Boris Aronov and Bernard M. Chazelle and Herbert Edelsbrunner and Leonidas J. Guibas and Micha Sharir and R. Wenger},
  keywords = {k-sets},
  booktitle = {Proc. 6th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {112--115},
  year = {1990}}

@article{AurSch-IJCGA-92,
  title = {{A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams}},
  author = {Franz Aurenhammer and Otfried Schwarzkopf},
  keywords = {order-k voronoi},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {2},
  pages = {363--381},
  year = {1992}}

@inproceedings{AurSch-SCG-91,
  title = {{A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams}},
  author = {Franz Aurenhammer and Otfried Schwarzkopf},
  keywords = {order-k voronoi},
  booktitle = {Proc. 7th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {142--151},
  year = {1991}}

@article{BarFurLov-Comb-90,
  title = {{On the number of halving planes}},
  author = {Imre B{\'a}r{\'a}ny and Zolt{\'a}n F{\"u}redi and L{\'a}szl{\'o} Lov{\'a}sz},
  keywords = {k-sets},
  journal = {Combinatorica},
  volume = {10},
  pages = {175--183},
  year = {1990}}

@inproceedings{BarFurLov-SCG-89,
  title = {{On the number of halving planes}},
  author = {Imre B{\'a}r{\'a}ny and Zolt{\'a}n F{\"u}redi and L{\'a}szl{\'o} Lov{\'a}sz},
  keywords = {k-sets},
  booktitle = {Proc. 5th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {140--144},
  year = {1989}}

@inproceedings{BarSte-CCCG-90,
  title = {{On the expected number of $k$-sets}},
  author = {Imre B{\'a}r{\'a}ny and William Steiger},
  keywords = {k-sets},
  journal = {Proc. 2nd Canad. Conf. Computational Geometry},
  pages = {55--59},
  year = {1990}}

@techreport{Bha-TR-83,
  title = {{An algorithm for computing order $k$ Voronoi diagrams in the plane}},
  author = {B. Bhattacharya},
  keywords = {order-k voronoi},
  institution = {Simon Fraser Univ., Computer Science Dept.},
  number = {83-9},
  year = {1983}}

@article{BoiDevTei-Algo-93,
  title = {{A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis}},
  author = {Jean-Daniel Boissonnat and O. Devillers and Monique Teillaud},
  keywords = {order-k voronoi},
  journal = {Algorithmica},
  volume = {9},
  pages = {329--356},
  year = {1993}}

@inproceedings{BoiDevTei-CCCG-90,
  title = {{A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis}},
  author = {Jean-Daniel Boissonnat and O. Devillers and Monique Teillaud},
  keywords = {order-k voronoi},
  journal = {Proc. 2nd Canad. Conf. Computational Geometry},
  pages = {278--281},
  year = {1990}}

@techreport{BoiDevTei-TR-90,
  title = {{A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis}},
  author = {Jean-Daniel Boissonnat and O. Devillers and Monique Teillaud},
  keywords = {order-k voronoi},
  institution = {INRIA Sophia-Antipolis},
  number = {1207},
  year = {1990}}

@article{CamMafVer-MP-89,
  title = {{Multi-constrained matroidal knapsack problems}},
  author = {P. M. Camerini and F. Maffioli and C. Vercellis},
  keywords = {parametric optimization, matroids},
  journal = {Mathematical Programming},
  volume = {45},
  pages = {211--231},
  year = {1989}}

@unpublished{Car-BC-84,
  title = {{Parametric cost shortest path problems}},
  author = {P. J. Carstensen},
  keywords = {parametric optimization, lower bounds},
  month = {8 May},
  year = {1984},
  note = {Unpublished Bellcore memo, available from the Literaturstelle at the Inst. f{\"u}r {\"O}konometrie und Operations Research, U. Bonn}}

@article{Car-MP-83,
  title = {{Complexity of some parametric integer and network programming problems}},
  author = {P. J. Carstensen},
  keywords = {parametric optimization},
  journal = {Mathematical Programming},
  volume = {26},
  number = {1},
  pages = {64--75},
  month = {May},
  year = {1983},
  abstract = {Two examples of parametric cost programming problems-one in network programming and one in NP-hard 0-1 programming-are given; in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables in the problem.}}

@phdthesis{Car-PhD-83,
  title = {{The complexity of some problems in parametric linear and combinatorial programming}},
  author = {P. J. Carstensen},
  keywords = {parametric optimization},
  school = {Univ. of Michigan},
  year = {1983}}

@article{Cha-Nw-77,
  title = {{Minimal ratio spanning trees}},
  author = {R. Chandrasekaran},
  keywords = {parametric optimization, minimum spanning tree},
  journal = {Networks},
  volume = {7},
  pages = {335--342},
  year = {1977}}

@inproceedings{ChaEde-SCG-85,
  title = {{An improved algorithm for constructing $k$th-order Voronoi diagrams}},
  author = {Bernard M. Chazelle and Herbert Edelsbrunner},
  keywords = {order-k voronoi},
  booktitle = {Proc. 1st Symp. Computational Geometry},
  publisher = {ACM},
  pages = {228--234},
  year = {1985}}

@article{ChaEde-TC-87,
  title = {{An improved algorithm for constructing $k$th-order Voronoi diagrams}},
  author = {Bernard M. Chazelle and Herbert Edelsbrunner},
  keywords = {order-k voronoi},
  journal = {Trans. Comput.},
  publisher = {IEEE},
  volume = {C-36},
  pages = {1349--1354},
  year = {1987}}

@article{ChaPre-DCG-86,
  title = {{Halfspace range search: an algorithmic application of $k$-sets}},
  author = {Bernard M. Chazelle and Franco P. Preparata},
  keywords = {k-sets},
  journal = {Discrete {\&} Computational Geometry},
  volume = {1},
  number = {1},
  pages = {83--94},
  year = {1986}}

@inproceedings{ChaPre-SCG-85,
  title = {{Halfspace range search: an algorithmic application of $k$-sets}},
  author = {Bernard M. Chazelle and Franco P. Preparata},
  keywords = {k-sets},
  booktitle = {Proc. 1st Symp. Computational Geometry},
  publisher = {ACM},
  pages = {107--115},
  year = {1985}}

@article{ClaEdeGui-DCG-90,
  title = {{Combinatorial complexity bounds for arrangements of curves and surfaces}},
  author = {Kenneth L. Clarkson and Herbert Edelsbrunner and Leonidas J. Guibas and Micha Sharir and Emo Welzl},
  keywords = {many faces},
  journal = {Discrete {\&} Computational Geometry},
  volume = {5},
  pages = {99--160},
  year = {1990}}

@article{ClaSho-DCG-89,
  title = {{Applications of random sampling in computational geometry II}},
  author = {Kenneth L. Clarkson and Peter W. Shor},
  keywords = {k-sets},
  journal = {Discrete {\&} Computational Geometry},
  volume = {4},
  pages = {387--421},
  year = {1989}}

@article{Col-JACM-87,
  title = {{Slowing down sorting networks to obtain faster sorting algorithms}},
  author = {Richard Cole},
  keywords = {parametric optimization},
  journal = {J. Assoc. Comput. Mach.},
  publisher = {ACM},
  volume = {34},
  number = {1},
  pages = {200--208},
  year = {1987}}

@article{ColShaYap-SJC-87,
  title = {{On $k$-hulls and related problems}},
  author = {Richard Cole and Micha Sharir and Chee K. Yap},
  keywords = {k-sets},
  journal = {SIAM J. Computing},
  volume = {16},
  pages = {61--77},
  year = {1987}}

@article{DeyEde-DCG-94,
  title = {{Counting triangle crossings and halving planes}},
  author = {Tamal K. Dey and Herbert Edelsbrunner},
  keywords = {k-sets},
  journal = {Discrete {\&} Computational Geometry},
  volume = {12},
  pages = {281--289},
  year = {1994}}

@inproceedings{DeyEde-SCG-93,
  title = {{Counting triangle crossings and halving planes}},
  author = {Tamal K. Dey and Herbert Edelsbrunner},
  keywords = {k-sets},
  booktitle = {Proc. 9th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {270--273},
  year = {1993}}

@article{EdeGuiSha-DCG-90,
  title = {{The complexity and construction of many faces in arrangements of lines and of segments}},
  author = {Herbert Edelsbrunner and Leonidas J. Guibas and Micha Sharir},
  keywords = {many faces},
  journal = {Discrete {\&} Computational Geometry},
  volume = {5},
  pages = {161--196},
  year = {1990}}

@techreport{EdeSto-TR-84,
  title = {{The number of extreme pairs of finite point-sets in Euclidean spaces}},
  author = {Herbert Edelsbrunner and G. St{\"o}ckl},
  keywords = {k-sets},
  institution = {Technische Univ. Graz, Inst. f{\"u}r Informationsverarbeitung},
  number = {F142},
  year = {1984}}

@inproceedings{EdeValWel-SCG-94,
  title = {{Cutting dense point sets in half}},
  author = {Herbert Edelsbrunner and P. Valtr and Emo Welzl},
  keywords = {k-sets},
  booktitle = {Proc. 10th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {203--210},
  year = {1994}}

@article{EdeWel-JCTA-85,
  title = {{On the number of line separations of a finite set in the plane}},
  author = {Herbert Edelsbrunner and Emo Welzl},
  keywords = {k-sets},
  journal = {J. Combinatorial Theory, Ser. A},
  volume = {38},
  pages = {15--29},
  year = {1985}}

@article{EdeWel-JCTA-86,
  title = {{On the maximal number of edges of many faces in an arrangement}},
  author = {Herbert Edelsbrunner and Emo Welzl},
  keywords = {many faces},
  journal = {J. Combinatorial Theory, Ser. A},
  volume = {41},
  pages = {159--166},
  year = {1986}}

@incollection{EdeWel-LNCS-84,
  title = {{Monotone edge sequences in line arrangements, with applications}},
  author = {Herbert Edelsbrunner and Emo Welzl},
  keywords = {levels},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  number = {176},
  pages = {265--273},
  year = {1984}}

@article{EdeWel-SJC-86,
  title = {{Constructing belts in two-dimensional arrangements with applications}},
  author = {Herbert Edelsbrunner and Emo Welzl},
  keywords = {levels},
  journal = {SIAM J. Computing},
  volume = {15},
  pages = {271--284},
  year = {1986}}

@article{EisSev-JACM-76,
  title = {{Mathematical techniques for efficient record segmentation in large shared databases}},
  author = {M. J. Eisner and D. G. Severance},
  keywords = {parametric optimization},
  journal = {J. Assoc. Comput. Mach.},
  publisher = {ACM},
  volume = {23},
  pages = {619--635},
  year = {1976}}

@article{Epp-JCTA-93,
  title = {{Improved bounds for intersecting triangles and halving planes}},
  author = {David Eppstein},
  keywords = {k-sets},
  journal = {J. Combinatorial Theory, Ser. A},
  volume = {62},
  pages = {176--182},
  year = {1993}}

@inproceedings{Epp-STOC-95,
  title = {{Geometric lower bounds for parametric matroid optimization}},
  author = {David Eppstein},
  keywords = {parametric optimization, lower envelopes, many faces, minimum spanning tree, matroids, lower bounds},
  booktitle = {Proc. 27th Symp. Theory of Computing},
  publisher = {ACM},
  pages = {662--671},
  year = {1995}}

@techreport{Epp-TR-91,
  title = {{Improved bounds for intersecting triangles and halving planes}},
  author = {David Eppstein},
  keywords = {k-sets},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer Science},
  number = {91-53},
  year = {1991}}

@techreport{Epp-TR-92,
  title = {{Sets of points with many halving lines}},
  author = {David Eppstein},
  keywords = {k-sets},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer Science},
  number = {92-86},
  year = {1992}}

@techreport{Epp-TR-95,
  title = {{Geometric lower bounds for parametric matroid optimization}},
  author = {David Eppstein},
  keywords = {parametric optimization, lower envelopes, many faces, minimum spanning tree, matroids, lower bounds},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer Science},
  number = {95-11},
  year = {1995}}

@article{EppHir-Algs-?,
  title = {{Choosing subsets with maximum weighted average}},
  author = {David Eppstein and Daniel S. Hirschberg},
  keywords = {parametric optimization},
  journal = {J. Algorithms},
  note = {To appear}}

@techreport{EppHir-TR-95,
  title = {{Choosing subsets with maximum weighted average}},
  author = {David Eppstein and Daniel S. Hirschberg},
  keywords = {parametric optimization},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer Science},
  number = {95-12},
  year = {1995}}

@incollection{ErdLovSim-SCT-73,
  title = {{Dissection graphs of planar point sets}},
  author = {Paul Erd{\"o}s and L{\'a}szl{\'o} Lov{\'a}sz and A. Simmons and E. G. Straus},
  keywords = {k-sets},
  booktitle = {A Survey of Combinatorial Theory},
  publisher = {North-Holland},
  pages = {139--149},
  year = {1973}}

@inproceedings{EveRobKre-SCG-93,
  title = {{An optimal algorithm for computing ($\le k$)-levels, with applications to separation and transversal problems}},
  author = {Hazel Everett and Jean-Marc Robert and Marc van Kreveld},
  keywords = {levels},
  booktitle = {Proc. 9th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {38--46},
  year = {1993}}

@article{FerSlu-Algs-94,
  title = {{Parametric problems on graphs of bounded tree-width}},
  author = {David Fern{\'a}ndez-Baca and Giora Slutzki},
  keywords = {parametric optimization},
  journal = {J. Algorithms},
  volume = {16},
  number = {3},
  pages = {408--430},
  year = {1994},
  review = {MR-95e:90111}}

@article{MR-95e:90111,
  reviews = {FerSlu-Algs-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Parametric problems on graphs of bounded tree-width}},
  author = {Peter Gritzmann},
  number = {95e:90111},
  year = {1995}}

@article{FerSlu-Algs-?,
  title = {{Optimal parametric search on graphs of bounded tree-width}},
  author = {David Fern{\'a}ndez-Baca and Giora Slutzki},
  keywords = {parametric optimization},
  journal = {J. Algorithms},
  note = {To appear}}

@inproceedings{FerSlu-LATIN-95,
  title = {{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
  author = {David Fern{\'a}ndez-Baca and Giora Slutzki},
  keywords = {parametric optimization, minimum spanning tree},
  booktitle = {Proc. 2nd Latin Amer. Symp. Theoretical Informatics},
  number = {911},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {257--271},
  year = {1995}}

@inproceedings{FerSlu-STACS-88,
  title = {{Solving parametric problems on trees}},
  author = {David Fern{\'a}ndez-Baca and Giora Slutzki},
  keywords = {parametric optimization},
  booktitle = {Proc. 5th Symp. Theor. Aspects of Computer Science},
  number = {294},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {52--60},
  year = {1988},
  review = {MR-89e:68099}}

@article{MR-89e:68099,
  reviews = {FerSlu-STACS-88},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Solving parametric problems on trees}},
  author = {Peter Eades},
  number = {89e:68099},
  year = {1989}}

@inproceedings{FerSlu-SWAT-92,
  title = {{Parametric problems on graphs of bounded tree-width}},
  author = {David Fern{\'a}ndez-Baca and Giora Slutzki},
  keywords = {parametric optimization},
  booktitle = {Proc. 3rd Scand. Worksh. Algorithm Theory},
  number = {621},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {304--316},
  year = {1992},
  review = {MR-94h:90064}}

@article{MR-94h:90064,
  reviews = {FerSlu-SWAT-92},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Parametric problems on graphs of bounded tree-width}},
  number = {94h:90064},
  year = {1994}}

@inproceedings{FerSlu-SWAT-94,
  title = {{Optimal parametric search on graphs of bounded tree-width}},
  author = {David Fern{\'a}ndez-Baca and Giora Slutzki},
  keywords = {parametric optimization},
  booktitle = {Proc. 4th Scand. Worksh. Algorithm Theory},
  number = {824},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {155--166},
  year = {1994},
  review = {MR-95k:68065}}

@article{MR-95k:68065,
  reviews = {FerSlu-SWAT-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Optimal parametric search on graphs of bounded tree-width}},
  number = {95k:68065},
  year = {1995}}

@article{FerSluEpp-NJC-?,
  title = {{Using sparsification for parametric minimum spanning tree problems}},
  author = {David Fern{\'a}ndez-Baca and Giora Slutzki and David Eppstein},
  keywords = {parametric optimization, minimum spanning tree},
  journal = {Nordic J. Computing},
  note = {To appear}}

@inproceedings{FerSluEpp-SWAT-96,
  title = {{Using sparsification for parametric minimum spanning tree problems}},
  author = {David Fern{\'a}ndez-Baca and Giora Slutzki and David Eppstein},
  keywords = {parametric optimization, minimum spanning tree},
  booktitle = {Proc. 5th Scand. Worksh. Algorithm Theory},
  number = {1097},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  month = {July},
  year = {1996}}

@article{FruBurRot-EJOR-89,
  title = {{Approximation of convex curves with application to the bicriterial minimum cost flow problem}},
  author = {B. Fruhwirth and R. E. Burkard and G{\"u}nter Rote},
  keywords = {parametric optimization},
  journal = {Eur. J. Oper. Res.},
  volume = {42},
  number = {3},
  pages = {326--338},
  year = {1989},
  review = {MR-91e:90107}}

@article{MR-91e:90107,
  reviews = {FruBurRot-EJOR-89},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Approximation of convex curves with application to the bicriterial minimum cost flow problem}},
  author = {Horst W. Hamacher},
  number = {91e:90107},
  year = {1991}}

@article{GabGalSpe-Comb-86,
  title = {{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
  author = {Harold N. Gabow and Zvi Galil and Thomas H. Spencer and Robert E. Tarjan},
  keywords = {minimum spanning tree},
  journal = {Combinatorica},
  volume = {6},
  pages = {109--122},
  year = {1986}}

@article{GolTar-JACM-89,
  title = {{Finding minimum-cost circulations by cancelling negative cycles}},
  author = {Andrew V. Goldberg and Robert E. Tarjan},
  keywords = {parametric optimization},
  journal = {J. Assoc. Comput. Mach.},
  publisher = {ACM},
  volume = {36},
  pages = {873--886},
  year = {1989}}

@article{GooPol-JCTA-84,
  title = {{On the number of $k$-subsets of a set of $n$ points in the plane}},
  author = {Jacob E. Goodman and Richard Pollack},
  keywords = {k-sets},
  journal = {J. Combinatorial Theory, Ser. A},
  volume = {36},
  pages = {101--104},
  year = {1984}}

@inproceedings{Gus-HCGT-79,
  title = {{Bounds for the parametric minimum spanning tree problem}},
  author = {Dan Gusfield},
  keywords = {parametric optimization, minimum spanning tree},
  booktitle = {Proc. Humbolt Conf. Graph Theory, Combinatorics and Computing},
  publisher = {Utilitas Mathematica},
  number = {XXVI},
  series = {Congress. Numer.},
  pages = {173--183},
  year = {1979},
  review = {MR-82f:68066}}

@article{MR-82f:68066,
  reviews = {Gus-HCGT-79},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Bounds for the parametric minimum spanning tree problem}},
  author = {Claude Benzaken},
  number = {82f:68066},
  year = {1988}}

@article{Gus-JACM-83,
  title = {{Parametric combinatorial computing and a problem in program module allocation}},
  author = {Dan Gusfield},
  keywords = {parametric optimization},
  journal = {J. Assoc. Comput. Mach.},
  publisher = {ACM},
  volume = {30},
  number = {3},
  pages = {551--563},
  year = {1983}}

@techreport{Gus-TR-80,
  title = {{Sensitivity analysis for combinatorial optimization}},
  author = {Dan Gusfield},
  keywords = {parametric optimization},
  institution = {Univ. of California, Berkeley},
  number = {UCB/ERL M80/22},
  month = {May},
  year = {1980}}

@article{GusBalNao-Algo-94,
  title = {{Parametric optimization of sequence alignment}},
  author = {Dan Gusfield and K. Balasubramanian and D. Naor},
  keywords = {parametric optimization},
  journal = {Algorithmica},
  volume = {12},
  pages = {312--326},
  year = {1994}}

@inproceedings{GusBalNao-SODA-92,
  title = {{Parametric optimization of sequence alignment}},
  author = {Dan Gusfield and K. Balasubramanian and D. Naor},
  keywords = {parametric optimization},
  booktitle = {Proc. 3rd Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {432--439},
  year = {1992}}

@article{GusMar-Algo-92,
  title = {{A fast algorithm for the generalized parametric minimum cut problem and applications}},
  author = {Dan Gusfield and Charles Martel},
  keywords = {parametric optimization},
  journal = {Algorithmica},
  volume = {7},
  number = {5},
  pages = {499--519},
  year = {1992},
  review = {MR-93b:90072}}

@article{MR-93b:90072,
  reviews = {GusMar-Algo-92},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{A fast algorithm for the generalized parametric minimum cut problem and applications}},
  author = {Peter Butkovic},
  number = {93b:90072},
  year = {1993}}

@article{HalSha-IPL-94,
  title = {{On disjoint concave chains in arrangements of (pseudo) lines}},
  author = {Dan Halperin and Micha Sharir},
  keywords = {many faces},
  journal = {Information Processing Letters},
  volume = {51},
  pages = {53--56},
  year = {1994}}

@article{HamRen-ORL-91,
  title = {{Color constrained combinatorial optimization problems}},
  author = {Horst W. Hamacher and Franz Rendl},
  keywords = {parametric optimization},
  journal = {Oper. Res. Lett.},
  volume = {10},
  number = {4},
  pages = {211--219},
  year = {1991},
  review = {MR-92h:90102}}

@article{MR-92h:90102,
  reviews = {HamRen-ORL-91},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Color constrained combinatorial optimization problems}},
  number = {92h:90102},
  year = {1992}}

@article{HarSha-Comb-86,
  title = {{Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes}},
  author = {S. Hart and Micha Sharir},
  keywords = {lower envelopes, lower bounds},
  journal = {Combinatorica},
  volume = {6},
  pages = {151--177},
  year = {1986}}

@inproceedings{HasImaIna-PCCGA-93,
  title = {{Efficient algorithms for variance-based $k$-clustering}},
  author = {Susumu Hasegawa and Hiroshi Imai and Mary Inaba and Naoki Katoh and Jun Nakano},
  keywords = {order-k voronoi},
  booktitle = {Proc. 1st Pacific Conf. Computer Graphics Appl.},
  publisher = {World Scientific},
  volume = {1},
  pages = {75--89},
  year = {1993}}

@article{HasTam-MOR-89,
  title = {{Maximizing classes of two-parametric objectives over matroids}},
  author = {Refael Hassin and A. Tamir},
  keywords = {parametric optimization, matroids},
  journal = {Math. Oper. Res.},
  volume = {14},
  pages = {362--375},
  year = {1989}}

@inproceedings{HerSno-SWAT-92,
  title = {{Convex polygons made from few lines and convex decompositions of polyhedra}},
  author = {John E. Hershberger and Jack Snoeyink},
  keywords = {many faces},
  booktitle = {Proc. 3rd Scand. Worksh. Algorithm Theory},
  number = {621},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {376--387},
  year = {1992}}

@inproceedings{HuaPevMil-CPM-94,
  title = {{Parametric recomputing in alignment graphs}},
  author = {Xiaoqiu Huang and Pavel A. Pevzner and Webb Miller},
  keywords = {parametric optimization},
  booktitle = {Proc. 5th Symp. Combinatorial Pattern Matching},
  number = {807},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {87--101},
  year = {1994},
  review = {MR-95d:92012}}

@article{MR-95d:92012,
  reviews = {HuaPevMil-CPM-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Parametric recomputing in alignment graphs}},
  number = {95d:92012},
  year = {1995}}

@article{IshShiNis-DAM-81,
  title = {{Stochastic spanning tree problem}},
  author = {H. Ishii and S. Shiode and T. Nishida},
  keywords = {parametric optimization, minimum spanning tree},
  journal = {Discrete Applied Mathematics},
  volume = {3},
  pages = {263--273},
  year = {1981}}

@article{KarKleTar-JACM-95,
  title = {{A randomized linear-time algorithm for finding minimum spanning trees}},
  author = {David Karger and Philip N. Klein and Robert E. Tarjan},
  keywords = {minimum spanning tree},
  journal = {J. Assoc. Comput. Mach.},
  publisher = {ACM},
  volume = {42},
  pages = {321--329},
  year = {1995}}

@article{KarOrl-DAM-81,
  title = {{Parametric shortest path algorithms with an application to cyclic staffing}},
  author = {Richard M. Karp and J. B. Orlin},
  keywords = {parametric optimization},
  journal = {Discrete Applied Mathematics},
  volume = {3},
  pages = {37--45},
  year = {1981}}

@article{Kat-ORSJ-89,
  title = {{An efficient algorithm for bicriteria minimum-cost circulation problems}},
  author = {Naoki Katoh},
  keywords = {parametric optimization},
  journal = {J. Oper. Res. Soc. Japan},
  volume = {32},
  number = {4},
  pages = {420--440},
  year = {1989},
  review = {MR-90j:90137}}

@article{MR-90j:90137,
  reviews = {Kat-ORSJ-89},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{An efficient algorithm for bicriteria minimum-cost circulation problems}},
  number = {90j:90137},
  year = {1990}}

@techreport{KatIba-TR-83,
  title = {{On the total number of pivots required for certain parametric combinatorial optimization problems}},
  author = {Naoki Katoh and T. Ibaraki},
  keywords = {parametric optimization, matroids},
  type = {Working Paper},
  institution = {Kobe Univ. Commerce, Inst. Econ. Res.},
  number = {71},
  year = {1983}}

@article{KatIwa-IJCGA-95,
  title = {{Finding $k$ farthest pairs and $k$ closest/farthest bichromatic pairs for points in the plane}},
  author = {Naoki Katoh and Kazuo Iwano},
  keywords = {order-k voronoi},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {5},
  pages = {37--51},
  year = {1995}}

@inproceedings{KatIwa-SCG-92,
  title = {{Finding $k$ farthest pairs and $k$ closest/farthest bichromatic pairs for points in the plane}},
  author = {Naoki Katoh and Kazuo Iwano},
  keywords = {order-k voronoi},
  booktitle = {Proc. 8th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {320--329},
  year = {1992}}

@article{KatTokIwa-DCG-95,
  title = {{On minimum and maximum spanning trees of linearly moving points}},
  author = {Naoki Katoh and Takeshi Tokuyama and Kazuo Iwano},
  keywords = {parametric optimization, minimum spanning tree},
  journal = {Discrete {\&} Computational Geometry},
  volume = {13},
  number = {2},
  pages = {161--176},
  month = {March},
  year = {1995}}

@inproceedings{KatTokIwa-FOCS-92,
  title = {{On minimum and maximum spanning trees of linearly moving points}},
  author = {Naoki Katoh and Takeshi Tokuyama and Kazuo Iwano},
  keywords = {parametric optimization, minimum spanning tree},
  booktitle = {Proc. 33rd Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {396--405},
  year = {1992}}

@article{KruSch-NJC-94,
  title = {{A note on higher order Voronoi diagrams}},
  author = {J. W. Krussel and B. F. Schaudt},
  keywords = {order-k voronoi},
  journal = {Nordic J. Computing},
  volume = {1},
  pages = {268--272},
  year = {1994}}

@article{Lov-AUSB-71,
  title = {{On the number of halving lines}},
  author = {L{\'a}szl{\'o} Lov{\'a}sz},
  keywords = {k-sets},
  journal = {Ann. Univ. Sci. Budapest, E{\"o}tv{\"o}s, Sect. Math.},
  volume = {14},
  pages = {107--108},
  year = {1971}}

@article{LueMigRam-SJC-90,
  title = {{Linear programming with two variables per inequality in poly-log time}},
  author = {George S. Lueker and Nimrod Megiddo and Vijaya Ramachandran},
  keywords = {parametric optimization},
  journal = {SIAM J. Computing},
  volume = {19},
  pages = {1000--1010},
  year = {1990}}

@article{Mat-DCG-91,
  title = {{Lower bounds on the length of monotone paths in arrangements}},
  author = {Ji{\v{r}}{\'\i} Matou{\v{s}}ek},
  keywords = {levels},
  journal = {Discrete {\&} Computational Geometry},
  volume = {6},
  pages = {129--134},
  year = {1991}}

@article{Meg-JACM-83,
  title = {{Applying parallel computation algorithms in the design of serial algorithms}},
  author = {Nimrod Megiddo},
  keywords = {parametric optimization},
  journal = {J. Assoc. Comput. Mach.},
  publisher = {ACM},
  volume = {30},
  number = {4},
  pages = {852--865},
  year = {1983}}

@article{Meg-MOR-79,
  title = {{Combinatorial optimization with rational objective functions}},
  author = {Nimrod Megiddo},
  keywords = {parametric optimization},
  journal = {Math. Oper. Res.},
  volume = {4},
  pages = {414--424},
  year = {1979}}

@article{Mul-DCG-91,
  title = {{On levels in arrangements and Voronoi diagrams}},
  author = {Ketan Mulmuley},
  keywords = {levels, order-k voronoi},
  journal = {Discrete {\&} Computational Geometry},
  volume = {6},
  pages = {307--338},
  year = {1991}}

@inproceedings{Mul-STOC-90,
  title = {{Output sensitive construction of levels and Voronoi diagrams in $\Re^d$ of order 1 to $k$}},
  author = {Ketan Mulmuley},
  keywords = {levels, order-k voronoi},
  booktitle = {Proc. 22nd Symp. Theory of Computing},
  publisher = {ACM},
  pages = {322--330},
  year = {1990}}

@article{PacSteSze-DCG-92,
  title = {{An upper bound on the number of planar $k$-sets}},
  author = {J{\'a}nos Pach and William Steiger and E. Szemer{\'e}di},
  keywords = {k-sets},
  journal = {Discrete {\&} Computational Geometry},
  volume = {7},
  pages = {109--123},
  year = {1992}}

@inproceedings{PacSteSze-FOCS-89,
  title = {{An upper bound on the number of planar $k$-sets}},
  author = {J{\'a}nos Pach and William Steiger and E. Szemer{\'e}di},
  keywords = {k-sets},
  booktitle = {Proc. 30th Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {72--79},
  year = {1989}}

@techreport{PacSteSze-TR-90,
  title = {{An upper bound on the number of planar $k$-sets}},
  author = {J{\'a}nos Pach and William Steiger and E. Szemer{\'e}di},
  keywords = {k-sets},
  institution = {Rutgers Univ., Ctr. for Discrete Math. {\&} Comp. Sci. (DIMACS)},
  number = {90-12},
  year = {1990}}

@article{Ram-DCG-96,
  title = {{The number of extreme triples of a point set}},
  author = {E. A. Ramos},
  keywords = {k-sets},
  journal = {Discrete {\&} Computational Geometry},
  volume = {16},
  number = {1},
  pages = {1--20},
  year = {1996}}

@inproceedings{RavGoe-SWAT-96,
  title = {{The constrained minimum spanning tree problem}},
  author = {R. Ravi and M. X. Goemans},
  keywords = {parametric optimization, minimum spanning tree},
  booktitle = {Proc. 5th Scand. Worksh. Algorithm Theory},
  number = {1097},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {66--75},
  year = {1996}}

@article{Ros-Algo-91,
  title = {{Order $k$ Voronoi diagrams of sites with additive weights in the plane}},
  author = {H. Rosenberger},
  keywords = {order-k voronoi},
  journal = {Algorithmica},
  volume = {6},
  pages = {153--181},
  year = {1991}}

@mastersthesis{Ros-MS-88,
  title = {{Order $k$ Voronoi diagrams of sites with additive weights in the plane}},
  author = {H. Rosenberger},
  keywords = {order-k voronoi},
  school = {Univ. Illinois, Urbana-Champaign, Dept. of Computer Science},
  year = {1988}}

@techreport{Ros-TR-88,
  title = {{Order $k$ Voronoi diagrams of sites with additive weights in the plane}},
  author = {H. Rosenberger},
  keywords = {order-k voronoi},
  institution = {Univ. Illinois, Urbana-Champaign, Dept. of Computer Science},
  number = {UIUCDCS-R-88-1431},
  year = {1988}}

@article{Ruh-Opt-88,
  title = {{Parametric maximal flows in generalized networks---complexity and algorithms}},
  author = {G. Ruhe},
  keywords = {parametric optimization},
  journal = {Optimization},
  volume = {19},
  number = {2},
  pages = {235--251},
  year = {1988},
  review = {MR-89e:90091}}

@article{MR-89e:90091,
  reviews = {Ruh-Opt-88},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Parametric maximal flows in generalized networks---complexity and algorithms}},
  author = {Rinnooy Kan, Alexander H. G.},
  number = {89e:90091},
  year = {1989}}

@article{Ruh-ZOR-88,
  title = {{Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh}},
  author = {G. Ruhe},
  keywords = {parametric optimization, lower bounds},
  journal = {Z. Oper. Res.},
  volume = {32},
  number = {1},
  pages = {9--27},
  year = {1988},
  note = {In German},
  review = {MR-89k:90059}}

@article{MR-89k:90059,
  reviews = {Ruh-ZOR-88},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh}},
  number = {89k:90059},
  year = {1989}}

@inproceedings{SchSpe-CCCG-91,
  title = {{On Delaunay and Voronoi diagrams of order $k$ in the plane}},
  author = {D. Schmitt and J.-C. Spehner},
  keywords = {order-k voronoi},
  booktitle = {Proc. 3rd Canad. Conf. Computational Geometry},
  pages = {29--32},
  year = {1991}}

@article{Sha-Comb-93,
  title = {{$k$-sets and random hulls}},
  author = {Micha Sharir},
  keywords = {k-sets},
  journal = {Combinatorica},
  volume = {13},
  pages = {483--495},
  year = {1993}}

@article{Sha-DCG-91,
  title = {{On $k$-sets in arrangements of curves and surfaces}},
  author = {Micha Sharir},
  keywords = {k-sets},
  journal = {Discrete {\&} Computational Geometry},
  volume = {6},
  pages = {593--613},
  year = {1991}}

@phdthesis{Sto-TUG-84,
  title = {{Gesammelte und neue Ergebnisse {\"u}ber extreme $k$-Mengen f{\"u}r ebene Punktmengen}},
  author = {G. St{\"o}ckl},
  keywords = {k-sets},
  type = {Diplomarbeit},
  school = {Technische Univ. Graz, Inst. f{\"u}r Informationsverarbeitung},
  year = {1984}}

@article{SzeTro-Comb-83,
  title = {{Extremal problems in discrete geometry}},
  author = {E. Szemer{\'e}di and William T. Trotter},
  journal = {Combinatorica},
  volume = {3},
  pages = {381--392},
  year = {1983}}

@inproceedings{TamTok-SCG-95,
  title = {{How to cut pseudo-parabolas into segments}},
  author = {Hisao Tamaki and Takeshi Tokuyama},
  keywords = {levels, parametric optimization, minimum spanning tree},
  booktitle = {Proc. 11th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {230--237},
  year = {1995}}

@incollection{Tol-CNC-93,
  title = {{Maximizing non-linear concave functions in fixed dimension}},
  author = {Sivan Toledo},
  keywords = {parametric optimization},
  booktitle = {Complexity in Numerical Computations},
  publisher = {World Scientific},
  editor = {Panos M. Pardalos},
  pages = {429--447},
  year = {1993}}

@inproceedings{Tol-FOCS-92,
  title = {{Maximizing non-linear concave functions in fixed dimension}},
  author = {Sivan Toledo},
  keywords = {parametric optimization},
  booktitle = {Proc. 33rd Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {676--685},
  year = {1992}}

@book{Wel-76,
  title = {{Matroid Theory}},
  author = {D. J. A. Welsh},
  keywords = {matroids},
  publisher = {Academic Press},
  year = {1976}}

@article{Wel-DCG-86,
  title = {{More on $k$-sets of finite sets in the plane}},
  author = {Emo Welzl},
  keywords = {k-sets},
  journal = {Discrete {\&} Computational Geometry},
  volume = {1},
  number = {1},
  pages = {95--100},
  year = {1986}}

@article{WieSha-DCG-88,
  title = {{Planar realizations of nonlinear Davenport-Schinzel sequences by segments}},
  author = {A. Wiernik and Micha Sharir},
  keywords = {lower envelopes, lower bounds},
  journal = {Discrete {\&} Computational Geometry},
  volume = {3},
  pages = {15--47},
  year = {1988}}

@article{YouTarOrl-Nw-91,
  title = {{Faster parametric shortest path and minimum-balance algorithms}},
  author = {N. E. Young and Robert E. Tarjan and J. B. Orlin},
  keywords = {parametric optimization},
  journal = {Networks},
  volume = {21},
  pages = {205--221},
  year = {1991}}