xennygrimmato's blog

By xennygrimmato, 11 years ago, In English

Given a set of n points and m transformations that are to be applied to each of the points, how can I perform the transformations in < O(nm)?

I tried to understand the solution to this from an article on e-maxx.ru/algo/binary_pow (its English translation), but I was unable to understand the method. Can someone help me out?

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it -13 Vote: I do not like it

From linear algebra we know that a combination of transformations performed sequentially is a transformation itself. Moreover, if all transformations are represented by a matrix, the resulting transformation is represented by a product of our matrices. That's all.

But the best answer for your question will be: just take a book in linear algebra and study it!