Зазначено, що деякі задачі геометричної оптимізації, наприклад пошук найменшого покриваючого еліпса множини точок, можна розв'язати за лінійний час, використовуючи нескладні випадкові (чи складні детерміновані) комбінаторні алгоритми. На практиці ці алгоритми поліпшують чи заміняють варіантами евристик, що працюють швидше, але теоретичні оцінки часу роботи для них не доведено. Запропоновано нову прискорювальну евристику, яку можна легко застосовувати до відомих лінійних алгоритмів, без зменшення їх швидкості у найгіршому випадку. Показано, що цю евристику можна визначити для будь-якої задачі з добре відомого класу задач лінійного програмування. Її ефективність на практиці залежить від того, чи можлива, і якщо можлива, то наскільки швидкою виявиться реалізація предиката для конкретної задачі. Наведено результати експериментів, які показують, що для двох задач нова евристика може значно прискорити існуючі реалізації алгоритмів (з бібліотеки геометричних алгоритмів CGAL).

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"