% 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}}