If these points represent "areas of interest" is this more about creating polygons around the points rather than connecting them? Voronoi is a very good way of doing this as it creates polygons where all locations in any polygon are closest to the original point than any other. However, it does not aggregate points by which I mean if many of these points are very close and represent something similar, they should be aggregated together before doing the process.
For example, if one town has 5 related landmarks and the next 3 are 20 miles away, it may not make sense to make 8 polygons. Maybe the 5 become one first!
Or as others have chimed in, if the points represent vertices of a polygon the problem is different.
Also any attribute data that groups them together makes the problem much more manageable.
------------------------------
Eric Blasenheim
Spectrum Spatial Technical Product Manager
Troy, NY
------------------------------