Проблема Супер Марио Гэлакси

Предположим, Марио ходит по поверхности планеты. Если он начнет идти из известного места в определенном направлении на заранее определенное расстояние, как быстро мы сможем определить, где он остановится?

$P$$s$$P$$v$$p$$\ell$$P$$P$

$P$$s$$v$$\ell$

$P$$O(1)$$\ell$$P$

(На практике длина пути на самом деле не является неограниченной; существует глобальная верхняя граница в терминах количества битов, необходимых для представления входных данных. Но настаивание на целочисленных входных данных поднимает некоторые довольно неприятные числовые проблемы - Как мы вычисляем точно, где чтобы остановить? - так что давайте придерживаться реальных входных данных и точной реальной арифметики.)

Известно ли что-нибудь нетривиальное о сложности этой проблемы?

$n$$[0,1]^2$$(0,1/2)$$(1,0)$$\lfloor \ell \rfloor$$\lfloor \ell \rfloor$$O(\log \ell)$$n$$\log \ell$

Эта проблема очень, очень сложная. Мы могли бы упростить это, чтобы сделать это проще, следующим образом.

1. $P$$\pi$

2. Можно предположить, что многогранник не является действительно трехмерным, но вместо этого является «двойником» многоугольника; это выглядит как наволочка. Мы можем упростить еще больше и предположить, что многоугольник имеет равные и параллельные стороны; например квадрат, как в игре Astroids.

$O(\log(\ell))$

Если мы не предполагаем рациональность, но предполагаем, что многогранник является двойником многоугольника, то мы обсуждаем теорию «разрезания последовательностей в иррациональных бильярдах». Кажется, что по существу здесь ничего не известно; например, см. последнее предложение этого выступления Коринны Улциграй.

Если мы не сделаем ни одного предположения, хорошо, я не могу думать ни о чем в литературе.

$O(\log(\ell))$

Я думаю, что вы можете сделать лучше, чем линейный. Я новичок в теоретической информатике, так что прости меня, если это мусор.

Некоторые общие идеи (различной ценности):

• Если мы дадим каждому аспекту символ, орбиту Марио над ними можно описать как строку, где последний символ в строке является ответом.
• Мы можем предположить без ограничения общности, что Марио начинает с ребра (просто идите назад и вытяните l к краю)
• 2D пространство начальных положений и углов может быть разделено следующим ребром. Таким образом, начиная с ребра a, на x единиц снизу, под углом a, мы переходим к ребру V после пересечения одной грани.
• В этот момент мы находимся на другом краю с другой ориентацией, поэтому мы можем рекурсивно вызывать функцию, чтобы разделить пространство на части 2-символьных строк и так далее.
• На этом мы заканчиваем, если говорим, что пространство должно быть дискретизировано, чтобы проблема была реализована на ТМ. Это означает, что каждая орбита должна быть периодической, потому что на дискретизированной планете существует только конечное число точек. Мы можем вычислить функцию, описанную выше, пока не получим орбиты для всех начальных точек и сохранить эту информацию. Тогда проблема становится O (1).
• Может быть, это что-то вроде полицейского. Некоторое гугление говорит мне, что почти все биллиардные орбиты внутри рациональных выпуклых многоугольников являются периодическими (т.е. периодические орбиты являются плотными). Так что для (скажем) квадратных планет такой же подход может сработать.
• Другой подход заключается в том, чтобы рассматривать систему как генератор / распознаватель строк (опять же, назначая каждому фасету свой символ). Если у языка есть известный класс сложности, это ваш ответ. Если вы расширите семейство многогранников до невыпуклых и любых измерений, вы можете охватить очень широкий класс языков.

Это на самом деле не является ответом, но мне нужно вернуться к работе. :)