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