Re: Closest Point Problem

From: Ash (amujoo_at_yahoo.com)
Date: 09/09/04

  • Next message: Marc Goodman: "Re: Closest Point Problem" 
    Date: 8 Sep 2004 23:25:43 -0700

    "Howard" <alicebt@hotmail.com> wrote in message news:<lFL%c.568582$Gx4.373652@bgtnsc04-news.ops.worldnet.att.net>...
    > "Ash" <amujoo@yahoo.com> wrote in message
    > news:60aab6b4.0409072328.63b1b627@posting.google.com...
    > > Given N points in space, what is the best possible algorithm to find k
    > > points closest to origin? What is the time complexity of the
    > > algorithm.
    > >
    > > Any solutions?
    > >
    > > Thanks
    > > ASH
    >
    > Computing time complexity was never my strong point, but how about this
    > method:
    >
    > Use a binary tree to store the smallest k numbers. Larger numbers go right,
    > smaller go left at any given node in the tree. That way, you can go right
    > from the root to find the point with the largest distance (of the k so far
    > stored) in, what, log k steps? Keep track of the size of the tree (in
    > number of points stored). When computing a new distance, see if the size is
    > k or greater. If it is, then find the node with the largest distance (by
    > going right until you can't go right any more - order log k, right?), and
    > delete that node (re-attaching its left child, if needed, to the parent of
    > that node or as a new root node, as appropriate). Then insert the new node
    > by traversing the tree to find its correct location (again, order log k,
    > right?). (Increment the size if it wasn't already at k.) When you're done
    > all the points, the tree holds the closest k, and a traversal of the tree
    > can give you those in order, if you like.
    >
    > So what is that complexity? O(n * (log k + log k))? Which would be O(2n
    > log k)? (Like I said, I suck at those computations! :-))
    >
    > -Howard

    I see that everybody is trying to convert the problem into a sorting
    or finding k smallest problem. May be that is the way of solving this,
    but I wonder if the "points in space" carries any significance. The
    coordinates given (x,y,z) for each point, do they hold any hint for
    the solution?

    - Ash

  • Next message: Marc Goodman: "Re: Closest Point Problem"

    Relevant Pages

    • Re: Closest Point Problem
      ... Computing time complexity was never my strong point, ... Use a binary tree to store the smallest k numbers. ... by traversing the tree to find its correct location (again, order log k, ... all the points, the tree holds the closest k, and a traversal of the tree ...
      (comp.theory)
    • Re: Closest Point Problem
      ... Ash wrote: ... > Given N points in space, what is the best possible algorithm to find k ... > points closest to origin? ... What is the time complexity of the ...
      (comp.theory)
    • LOS Optimization Using Binary Tree Structures (with demo)
      ... fast way to calculate LOS using a binary tree (properly called a binary ... describe the visibility-dependency between tiles - as in describing ... Using octants ... The cool thing about using a relational-based LOS algorithm is that you ...
      (rec.games.roguelike.development)
    • Re: How come Ada isnt more popular?
      ... beneficial for the memory-management aspect of such an algorithm. ... When the GC hits it just traverses the tree ... E.g a chess playing program (any ... Furthermore generational garbage collection AFAIK has ...
      (comp.lang.ada)
    • Re: Question about decision tree algorithm in sqlserver2000
      ... If your target, on the other hand, is continuous, the algorithm will build regression trees that have regression formulae in nodes and leaves. ... if your target is continuous (i.e. a regression tree) than the lift chart is replaced by a scatter plot ...
      (microsoft.public.sqlserver.datamining)