title: R tree and Graph partitioning library in R
body: <p>I need to make efficient d-dimensional points searching and also make efficient k-NN queries of a point in d-dimension. Therefore i require an R-Tree library. I require a library which will build the R-Tree structure, which i can use to query whenever needed.</p>
  
  <p>Also i need to have some library like that of <a href="http://glaros.dtc.umn.edu/gkhome/metis/metis/overview" rel="nofollow">METIS</a> or <a href="http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview" rel="nofollow">hMETIS</a>, although my application does not involve hypergraphs. My requirement is to find the min cut set of a graph which divides the graph in roughly two equal sized graphs.</p>
  
  <p>The thing is i would require libraries which support these in R.</p>
  
  <p>I have found a library <a href="http://cran.r-project.org/web/packages/RANN/index.html" rel="nofollow">RANN</a>, which has kd-tree based k-NN queries, but the problem is that either i have to make all the k-NN queries at once and store the results in a huge array, or need to call the function (<code>nn</code> or <code>nn2</code>) every time i need, which defeates the O(n lg n) retrieval growth of time. </p>
  
  <p>Can anyone tell me if there is any such libraries in R?</p>
  
  <p><em>Note:</em> I would require the R-Tree library for implementing clustering algorithms efficiently, and the graph partition library would be required to implement the CHAMELEON clustering algorithm.</p>