%-------------------------
% Selection / Search
%-------------------------
@article
 {tar,
  author="R. Tarjan",
  title="A class of algorithms which requires nonlinear time to
         maintain disjoints sets",
  journal="J. of Computer and system sciences",
  year="1979",
  volume="18",
  number="",
  pages="110-127"
}

@article
 {yao1,
  author="A. Yao",
  title="On the complexity of maintaining partial sums",
  journal="SIAM J. Computing",
  year="1985",
  volume="14",
  number="2",
  pages=""
}

@article
 {wil1,
  author="D. Willard",
  title="Log-Logarithmic worst-case range queries are possible in
         space $\Theta(n)$",
  journal="Information Processing Letters",
  year="1983",
  volume="17",
  number="",
  pages="81-84"
}

@article
 {ben,
  author="JL. Bentley",
  title="Multidimensional divide-and-conquer",
  journal="Communications of the ACM",
  year="1980",
  volume="23",
  number="4",
  pages="214-229"
}

@article
 {lp,
  author="D. Lee and F. Preparata",
  title="Location of a point in a planar subdivision and its
         applications",
  journal="SIAM J. Computing",
  year="1977",
  volume="6",
  number="3",
  pages="594-606              "
}



@article
 {hs,
  author="H. Samet",
  title="Hierarchical Representations of collections of small
         rectangles",
  journal="ACM computing surveys",
  year="1988",
  volume="20",
  number="4",
  pages=""
}



@inproceedings
 {col1,
  author="R. Cole and others",
  title="Optimal slope selection",
  booktitle="Proc. 15 th ICALP",
  year="1988",
  pages="133-146"
 }


@article
 {ede1,
  author="H. Edelsbrunner and L. Guibas and J. Stolfi",
  title="Optimal point location in a monotone subdivision",
  journal="SIAM J. On Computing",
  year="1986",
  volume="15",
  number="2",  
  pages=""
 }

@article
 {wil2,
  author="D. Willard",
  title="Polygon Retrieval",
  journal="SIAM J. on Computing",
  year="1982",
  volume="11",
  number="1",  
  pages=""
 }

@article
 {yao2,
  author="A. Yao and F. Yao",
  title="A General Approach to d-dimensional Geometric Queries",
  booktitle="ACM STOC",
  year="1985",
  pages="163-168"
 }


@article
 {rriv,
  author="R. Rivest",
  title="Partial-match retrieval algorithms",
  journal="SIAM J. Computing",
  year="1976",
  volume="5",
  number="1",
  pages="19-50"
}



@inproceedings
 {lue,
  author="G. Lueker",
  title="A data structure for orthogonal range queries",
  booktitle="$19^{th}$ IEEE FOCS",
  address="Ann Arbor (Michigan)",
  year="1978",
  pages="28-34"
}


@article
 {bf,
  author="JL. Bentley and J. Friedman",
  title="Data structures for range searching",
  journal="ACM computing surveys",
  year="1979",
  volume="11",
  number="4",
  pages=""
}



@techreport
 {br,
  author="B. Rosenberg",
  title="Lower bounds in geometric searching (Thesis)",
  number="CS-TR-343-91",
  institution="Princeton University",
  year="1991"
}


@article
 {cha1,
  author="B. Chazelle",
  title="A functional approach to data structures and its use
         in multidimensional searching",
  journal="SIAM J. Computing",
  year="1988",
  volume="17",
  number="3",
  pages=""
}


@article
 {cha2,
  author="B. Chazelle",
  title="Lower bounds for orthogonal range searching : 
         I The reporting case",
  journal="Journal of the ACM",
  year="1990",
  volume="37",
  number="2",
  pages=""
}


@article
 {cha3,
  author="B. Chazelle",
  title="Lower bounds for orthogonal range searching : 
         II The arithmetic model",
  journal="Journal of the ACM",
  year="1990",
  volume="37",
  number="3",
  pages=""
}

@article
 {wil3,
  author="D. Willard",
  title="New data structures for orthogonal range queries",
  journal="SIAM J Computing",
  year="1985",
  volume="14",
  number="1",
  pages=""
}

@article
 {bao,
  author="J. Bentley and others",
  title="The complexity of finding fixed-radius near neighbors",
  journal="Information Processing Letters",
  year="1977",
  volume="6",
  number="6",
  pages=""
}


@article
 {ab,
  author="A. Bolour",
  title="Optimal retrieval algorithms for small region queries",
  journal="SIAM J. Computing",
  year="1981",
  volume="10",
  number="",
  pages="721-741"
}


@article
 {lw,
  author="G. Lueker and D. Willard",
  title="A data structure for dynamic range queries",
  journal="Information Processing Letters",
  year="1982",
  volume="15",
  number="5",
  pages="209-213"
}


@article
 {bm,
  author="JL. Bentley and H. Maurer",
  title="Efficient worst-case data structures for range searching",
  journal="Acta Informatica",
  year="1980",
  volume="13",
  number="",
  pages="155-168"
}



@article
 {fre0,
  author="M. Fredman",
  title="The complexity of maintaining an array and computing
         its partial sums",
  journal="J. of the ACM",
  year="192",
  volume="29",
  number="1",
  pages="250-260"
}


@article
 {fre1,
  author="M. Fredman",
  title="A lower bound on the complexity of orthogonal range queries",
  journal="J. of the A.C.M",
  year="1981",
  volume="28",
  number="4",
  pages="696-705"
}

@article
 {bur,
  author="W. Burkhard and L. Fredman and D. Kleitman",
  title="Inherent complexity trade-offs for range query problems",
  journal="Theorical Computer Science",
  year="1981",
  volume="16",
  number="",
  pages="279-290"
}

@article
 {fre2,
  author="M. Fredman",
  title="Lower bounds on the complexity of some optimal data 
         structures",
  journal="SIAM J. Computing",
  year="1981",
  volume="10",
  number="1",
  pages="1-10"
}


@article
 {dye,
  author="M. Dyer",
  title="On a multidimensional search technique and its applications to the
         euclidean one-centre problem",
  journal="SIAM J. On Computing",
  year="1986",
  volume="15",
  number="3",  
  pages=""
 }

@article
 {cha2,
  author="B. Chazelle",
  title="Filtering search : a new approach to query-answering",
  journal="SIAM J. On Computing",
  year="1986",
  volume="15",
  number="3",  
  pages=""
 }

@inproceedings
 {cha4,
  author="B. Chazelle",
  title="Polytope Range Searching and Integral Geometry",
  booktitle="IEEE FOCS",
  year="1987",
  pages="1-10"
 }

@article
 {ede2,
  author="H. Edelsbrunner and E. Welzl",
  title="Halfplanar range search in linear space and $0(n^{0.695})$ time",
  journal="Information Processing Letters",
  year="1986",
  volume="23",
  number="",  
  pages="289-293"
 }


@inproceedings
 {ma0,
  author="J. Matousek",
  title="Range searching with efficient hierarchical cuttings",
  booktitle="$8^{th}$ ACM Conf. in Comp. Geom.",
  address="Berlin",
  year="1992",
  pages="276-285"
}



@article
 {ma1,
  author="J. Matousek",
  title="Range searching with efficient hierarchical cuttings",
  journal="Discrete and Computational Geometry",
  year="1993",
  volume="10",
  number="",
  pages="157-182"
}


@article
 {ma2,
  author="J. Matousek",
  title="Cutting hyperplanes arrangements",
  journal="Discrete and Computational Geometry",
  year="1991",
  volume="5",
  number="",
  pages="385-406"
}


@inproceedings
 {ma3,
  author="J. Matousek",
  title="Cutting hyperplane arrangements",
  booktitle="$6^{th}$ ACM Symp. in Comp. Geom.",
  address="Berkely",
  year="1990",
  pages="1-9"
}



@article
 {cha5,
  author="B. Chazelle",
  title="Cutting Hyperplanes for divide and conquer",
  journal="Discrete and Computational Geometry",
  year="1993",
  volume="9",
  number="",
  pages="145-158"
}

@article
 {ma4,
  author="J. Matousek",
  title="Efficient partition trees",
  journal="Discrete and Computational Geometry",
  year="1992",
  volume="8",
  number="",
  pages="315-334"
}

@article
 {cha6,
  author="B. Chazelle",
  title="Lower bounds on the complexity of polytope range searching",
  journal="J. of the American Mathematical Society",
  year="1989",
  volume="2",
  number="4",
  pages="637-666"
}

@article
 {cha7,
  author="B. Chazelle and E. Welzl",
  title="Quasi-optimal range searching in spaces of finite VC-dimension",
  journal="Discrete and Computational Geometry",
  year="1989",
  volume="4",
  number="",
  pages="467-489"
}


@inproceedings
 {csw,
  author="B. Chazelle and M. Sharir and E. Welzl",
  title="Quasi-optimal upper bounds for simplex range searching and
         new zone theorems",
  booktitle="$6^{th}$ ACM Symp. in Comp. Geom.",
  address="Berkeley",
  year="1990",
  pages="23-33"
}


@article
 {dl,
  author="D. Dobkin and R. Lipton",
  title="Multidimensional searching problems",
  journal="SIAM J. Computing",
  year="1976",
  volume="5",
  number="2",
  pages="181-186"
}

@article
 {js,
  author="J. Saxe",
  title="On the number of range queries in $k$-space",
  journal="Discrete Applied Mathematics",
  year="1979",
  volume="1",
  number="",
  pages="217-225"
}

@techreport
 {bs,
  author="J. Bentley and M. Shamos",
  title="A problem in multivariate statistics : algorithm, data
         structure and applications",
  number="CMU-CS-78-110",
  institution="Carnegie-Mellon university",
  year="1978"
}


%-------------------------
% Partition
%-------------------------
@article
 {col2,
  author="R. Cole",
  title="Partitioning Point sets in 4 dimensions",
  journal="",
  year="",
  volume="",
  number="",  
  pages=""
 }

@inproceedings
 {wel,
  author="E. Welzl",
  title="Partition trees for triangle counting and other range searching 
         problems",
  booktitle="4 th ACM Symp. on Computational Geometry",
  year="1988",
  pages="23-33"
 }


@inproceedings
 {pat,
  author="S. Paterson and F. Yao",
  title="Binary Partitions with applications to Hidden-Surface Removal
         and Solid Modelling",
  booktitle="5 th ACM Symp. on Computational Geometry",
  year="1989",
  pages="23-32"
 }



@inproceedings
 {Yao3,
  author="F. Yao",
  title="A 3-space partition and its applications",
  booktitle="ACM Symp. on the Theory of Computing",
  address="",
  year="1983",
  pages="258-263"
}



%------------------------------------
% Quadtrees
%------------------------------------
@article
 {btl,
  author="JL. Bentley and F. Stanat",
  title="Analysis of range searches in quad trees",
  journal="Information Processing Letters",
  year="1975",
  volume="3",
  number="6",
  pages=""
}


@article
 {lwx,
  author="D.T. Lee and C. Wong",
  title="Worst-case analysis for region and partial region searches
         in ultidimensional search trees and balanced quad trees",
  journal="Acta Informatica",
  year="1977",
  volume="9",
  number="",
  pages="23-29"
}


@article
 {fla,
  author="M. Hoshi and P. Flajolet",
  title="Page usage in a Quadtree index",
  journal="BIT",
  year="1992",
  volume="32",
  number="",
  pages="384-402"
}

@article
 {,
  author="H. Samet",
  title="The Quadtree and Related Hierarchical Data 
         Structures",
  journal="ACM Computing surveys",
  year="1984",
  volume="6",
  number="2",
  pages="187-260"
}




%------------------------------------
% k-d trees
%------------------------------------
@article
 {mo,
  author="M. Overmars",
  title="Geometric data structures for computer graphics :
         an overview", 
  journal="NATO ASI Series. Series F",
  year="1988",
  volume="40",
  number="",
  pages=""
}


@article
 {vko,
  author="M. van Kreveld and H. Overmars",
  title="Divided k-d Trees",
  journal="Algorithmica",
  year="1991",
  volume="6",
  number="",
  pages="840-858"
}


@article
 {ol1,
  author="M. Overmars and J. van Leeuwen",
  title="Dynamic multi-dimensional data structures",
  journal="Acta Informatica",
  year="1982",
  volume="17",
  number="",
  pages="267-285"
}

@article
 {ol2,
  author="M. Overmars and J. van Leeuwen",
  title="Two general methods for dynamizing decomposable searching 
         problems",
  journal="Computing",
  year="1981",
  volume="26",
  number="",
  pages=""
}

@article
 {btl1,
  author="JL. Bentley",
  title="Decomposable searching problems",
  journal="Information Processing Letters",
  year="1979",
  volume="8",
  number="5",
  pages="244-251"
}

@article
 {btl2,
  author="JL. Bentley",
  title="Multidimensional binary search trees in database applications",
  journal="IEEE Trans. on Software Engineering",
  year="1979",
  volume="5",
  number="4",
  pages=""
}

@article
 {btl3,
  author="JL. Bentley",
  title="Multidimenisonal binary search trees used for associative
         searching",
  journal="Communication of the ACM",
  year="1975",
  volume="18",
  number="9",
  pages="509-517"
}