How many right triangles can be built from points

There is an $\mathcal{O}(N^2\log N)$-time algorithm, coming from an ability to compute, for each point $P$, the number of right angles at $P$, in $\mathcal{O}(N\log N)$ time. This can be done by considering the (other) points in the polar coordinate system with the origin at $P$, and sorting by polar angle, after which the counting is easy. (Actually there's no need to compute the polar angles - this is just an idea to be used indirectly.)

Tags:

Python

Geometry

Triangles

Related

Does the Fundamental Theorem of Algebra follow from the real Spectral Theorem? A bijection $\phi:\mathbb R \to \mathbb R$ that must be an identity Use proof by mathematical induction to prove explicit formula for recursive sequence is correct Intuition behind the paradox of instantaneous heat propagation Show: $\int_0^1\int_0^1\frac{dx\,dt}{(xt)^2+xt+1}=\frac{2}{\sqrt3}\mathrm{Cl}_2\left(\tfrac{2\pi}{3}\right)$ Show that $\sum_{k=0}^{n+1}\left(\binom{n}{k}-\binom{n}{k-1}\right)^2 = \frac{2}{n+1}\binom{2n}{n}$ Show for isometry $T:V \rightarrow V$, $\frac{1}{n}\sum_{i=0}^{n-1} T^i$ converges to the orthogonal projection on $ker(T-I)$. Set of rapidly increasing functions is uncountable? Trying to solve a recurrence relation by using generating functions: $a_n=3a_{n-1} + a_{n-2}$ Field elements which become $n$th powers after adjoining an $n$th root of unity Squaring a simple inequality Every infinite group has a non-trivial subgroup

Recent Posts