New answers tagged efficiency
2
The whole "how to design efficient algorithms" theme is (surprise!) treated in books usually called "Algorithms" or sometimes a variation like "Introduction to Algorithms". Areas of active research (some more advanced textbooks available) are approximation algorithms (get a decent, not the best possible, solution with reasonable ...
3
Since your matrices are small $(50 \times 50)$, you can probably just compute $M^t$ through repeated exponentiation where the exponents are powers of $2$.
Write $t$ in binary so that $t = 2^{k_1} + 2^{k_2} + \dots + 2^{k_\ell}$.
Then $M^t = \prod_{i=1}^\ell M^{2^{k_i}}$. Moreover, for $k_i \ge 1$ you have $M^{2^{k_i}} = \left( M^{2^{k_i - 1}} \right)^2$, ...
1
I suggest using xtensor. You can compute the 4000-th matrix power of M as xt::linalg::matrix_power(M, 4000).
Obviously you should be aware that powering in any language can incur in numerical issues. Even if your matrix is 1 x 1, M^4000 could be enormous, larger than what you could store as a floating point value.
1
One approach would be to use dynamic programming. Pick 100 points $P_1,\dots,P_{100}$ along the spline. For each point $P_i$ on the spline, pick 5 points $Q_{i,-1},Q_{i,-1/2},Q_{i,0},Q_{i,1/2},Q_{i,1}$, where $Q_{i,0}=P_i$, $Q_{i,1}$ is $d$ away from $P_i$ in the direction perpendicular to the spline, $Q_{i,1}$ is $d$ away in the opposite direction, $Q_{i,...
1
A simple approach would be to take a dense sample of points on the spline (i.e., more than you need), and then apply the Ramer-Douglas-Peucker polyline simplification algorithm to get rid of as many of them as possible. Note: Unless you generate the point sample in some clever way (e.g., with density proportional to the local curvature), this isn't ...
Top 50 recent answers are included
