Нечисловой способ определить, находится ли точка в выпуклой оболочке или на ее границе

Question

У меня есть набор точек S в произвольном фиксированном измерении, заданных как кортежи в Python. Мне нужно знать, находится ли данная точка p внутри выпуклой оболочки S, на ее границе или снаружи. Это для математического доказательства, поэтому я не доволен численными расчетами. Я ищу точный ответ. Все мои точки рациональны (на самом деле, вы можете предположить, что они являются положительными целыми числами).

Желательно что-то уже реализованное или какая-то библиотека, а не алгоритм.

Answer 1

Используйте симплекс-метод с рациональной арифметикой. Решатель не должен входить в базу доверенных кодов, потому что первичное и двойственное решения вместе образуют сертификат.