I'm doing a homework problem that simplified is grouping stars into constellations given their x,y coordinates and a min distance. Any star can be a constellation by itself. so e.g 5 stars cant connect to each other then it will return that there are 5 constellations.
I've initially made an algorithm that checks each point with a runtime of O(n^2). I want to make it faster and saw that a DBSCAN runs in O(nlogn) time.
My question is that if I were to use a DBSCAN the algorithm says it will run in O(nlogn) time but if my minPts is 1 (the size of my clusters) will that negate the efficiency of the DBSCAN and run in O(n^2)??
As far as I'm concerned running time of a DBSCAN in this case depends on a calculation of neighbours, which is performed on each point, within the given distance. As you mentioned if you perform a linear scan you'd get O(n^2) in total. Nevertheless, in order to speed up a search you could use an index-based structure which searches in a O(logn) time. Please, checkout spatial databases.