About the analysis / performance algorithm?

Question

As shown in the figure, I have the following structures for storing the Curves cabinet set in Slice. A “curve” consists of “Nodes” implemented as a doubly linked list.

Here is the psuedo code:

class Slice { List<Curve*> curves; } class Curve { int objectID; Node *headNode; } class Node { double x, double y, Node *next; Node *previous } 

I draw this structure using the QT paint methods and I want to select the node closest to the mouse point.

What am I doing,

a). Get every “curve” in “Slice”

b) Go through all the nodes of the selected curve and calculate the distance from the mouse point to each point and compare.

My questions:

1) if we take the number of curves "c", and the middle nodes "n", the complexity of the algorithm is O (n * c). Is this analysis correct?

2) Is there a way to improve the algorithm, make it faster? Using a binary tree, HashTable..etc?

Answer 1

1) Yes, your analysis is correct

2) You can get the logarithmic complexity using the nearest neighbor search .

The simplest of all can be using the kd tree