1
$\begingroup$

I want to add a points one by one into sorting tree. I have less then function to order them by angle from absciss: for points $\mathbf p_i = (x_i,y_i)$ and $\mathbf p_j = (x_j,y_j)$ it just sign of cross product of radius vectors to them:

$$ f_<(\mathbf p_i, \mathbf p_j) \stackrel{def}{\equiv} (x_i \cdot y_j < x_j \cdot y_i) $$

How can I modify RB tree implementation (or is there more general approach for any sorting tree) to make it looped (i.e. modulo $2 \pi$)? Is there "symmetrical" approach to make tree equally well arranged with no dependence on direction for points in general positions?

$\endgroup$
  • $\begingroup$ What do you mean by "make it looped"? What are you taking modulo $2\pi$? If you just use the ordering directly without doing anything to "make it looped" is there some requirement that is violated? I'm having difficulty understanding what you're trying to accomplish. $\endgroup$ – D.W. Feb 3 '18 at 18:47
  • $\begingroup$ @D.W. On usual invariant for BST is !(least_element > greatest_element). It violated in case of modular arithmetic. $\endgroup$ – Orient Feb 3 '18 at 18:51
  • $\begingroup$ I know that, but I don't understand what you are trying to accomplish. What number/value do you want to apply modular arithmetic to? How will you recognize a valid answer? What requirements must it satisfy? Why is it a problem if you don't use "modulo" but just sort the points according to the "less than" function you defined? What are you trying to accomplish? $\endgroup$ – D.W. Feb 3 '18 at 19:02
  • $\begingroup$ It looks like you mean something like en.wikipedia.org/wiki/Cyclic_order - and it's not a binary relation $\endgroup$ – HEKTO Feb 4 '18 at 1:05
  • $\begingroup$ Also you need to define operations on data structure you are trying to develop - it will help you to understand how you need to store your data points $\endgroup$ – HEKTO Feb 4 '18 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.