convex hull is probably not what you want.  does your current algo give satisfactory results, but it just has performance problems?  does it work something like "for every point, search every other point to see who's closest"?  so if you have N points, you do N*N tests?  if so, that won't scale well.  perhaps try building a tree (quad-, or r-, or k-d, or etc) of your points to speed up the nearest-neighbor part of the algo.  you'll trade a bit more work up front building the tree, but could potentially save a ton of work later when searching it.