Dense point sets have sparse Delaunay triangulations: or "... but not too nasty".

Jeff Erickson

Browse the full SODA paper archive.