Это ведь правда мудрая мысль. Наверняка у тебя есть чем заняться, кроме ускорения поиска прямоугольников. Сначала убедись, что ускорять надо, а уже потом трать на это время. Всего-то нужно инкапсулировать функцию запроса, чтобы потом ее можно было легко переписать не тревожа остальной код - если будут тормоза. И вообще, как сказал кто-то из гуру, "самый надежный код - тот, которого нет".

Но, на всякий случай, на будущее:

Сортировать только по минимуму. Либо по максимуму. Разницы особой нет, зависит от  вида запросов. 
А размер (длину-ширину) учитывать уже при запросе, это ведь просто.

Добавлено через 8 минут и 48 секунд

Вовсе не все, а только до того прямоугольника, координата которого >= точки запроса (это если отсортировано по минимумам). И оставлять для дальнейшей проверки только те прямоугольники, у которых мин+длина <= точки запроса. То же самое по другой координате. Полученные списки пересечь.
Можно вообще оставить только один индекс, а попадание по другой координате проверять явно (для каждого прямоугольника из найденной последовательности). Число проверяемых прямоугольников существенно уменьшается.

Хорошо, давайте разберемся с этим.

Вот простейший случай 9 одинаковых кубиков. Кубики отсортированы по левому краю, порядковые номера в индексе показаны.
Допустим точка попала в центр. По индексу она попала между 6 и 7.
Итак с 7 по 9 мы точно отбрасываем. Необходимый кубик где-то ниже или равен 6. (т.е. в диапазоне 1...6)
Начинаем с 6 и вниз. До какого пробегать?

т.е меня интересует что поставить вместо END

for (int i= 6; i>END; --i)
   if (совпали?)
      break;

ИМХО простой перебор вседа самый долгий. Ну, если, конечно, у Вас не пара-тройка прямоугольников. Но я не утверждаю, что мое предложение самое быстрое.

Я поленился расписывать совсоем уж детально. Поэтому Вы и поняли это как многократные пробежки. Попробую уточнить.

• Отсортировать действительно надо 4 раза. Отдельно по кажой границе прямоугольников. Но Вы пишете, что время сотрировки значения не имеет - так что хоть 400 раз, но заранее - до поступления запроса на поиск точки (как я понял).
• Отбрасывать прямоугольники лежащие выше точки надо используя сортировку по нижней границе, ниже - по верхней и т.д. Отбрасывать надо из всего набора, естественно.
• Поиск в сортированном массиве надо проводить никак не пробежкой, а бинарным делением, например. Если на память ограничений нет, можно заранее построить бинарные деревья - быстрее будет.
• Закономерный вопрос - как отбрасывать, чтобы было быстро. Не размеры же массива каждый раз переустанавливать. На этот вопрос я не отвечу - все зависит от возможностей конкретного языка програмирования: какие в нем имеются структуры данных и сколь они быстры.

Еще раз - на звание разработчика самых быстрых алгоритмов я не претендую  

Да, ты прав, я спутала с одномерными интервалами. Ранее вроде предполагалось, что прямоугольники не пересекаются. Но проекции их запросто могут.
И доп. индексы тоже особо не спасают, т.к. скорее все запутывают. Можно, конечно, делать как предлагает Y: "отбрасывать" - фактически, вычислять пересечение  множеств - 2 или 4 (если по всем сторонам индексировать), но как-то это чересчур. 
Лучше уж кластеры.
ЗЫ
Есть еще способ отобразить плоскость в линию с помощью фракталов. В этом случае точки плоскости упорядочиваются в соответствии со своим порядком на фрактальной линии. Но это как-то слишком кучеряво для данной задачи.

В принципе к-д дерево, что предложил baldina и приводит к-мерное пространство к одномерной системе. 
(Это я своими словами.   , но помоему не далеко от сути ?)
Трудность только построить эффективное дерево автоматически...

Не, это как раз не очень трудно... похоже на деревья решений. Смысл в том, что каждый раз нужно выбрать "наиболее разделяющее" значение.
Просто страшно поначалу, потому что слова все такие умные. Это я свои впечатления излагаю, как раз недавно с Decision Tree разбиралась. Оказалось, если не сильно умничать со всякими там улучшениями, ничего страшного. Главное, действительно быстро (и строит и классифицирует).
Но это, конечно, не сведение к одномерной системе, а линейный классификатор. Но не в терминах суть.
Если у тебя есть время \ возможность \ желание заморачиваться, попробуй. Решение в самом деле красивое. 

 Подскажи, пожалуйста, где описано хорошо, коротко и, желательно, почти без примеров. Мне тоже интересно.
 

В Вики, конечно. Читать английский вариант. Потом идешь по ссылке на алгоритм ID3. Там где-то рядом есть и код, но не читабелен, имхо. Проще разобраться и написать самому. Без примеров вряд ли что-то найдешь; причем почему-то примеры всегда на редкость дебильные; при этом все про дискретный случай и про булевские функции (да\нет). Но для небулевских (несколько классов) строится точно так же (все эти энтропии и прочая хрень). Про действительные переменные тоже можно что-то найти, но в основном додумывается, после погружения в тему. Я весь поиск начинала с Вики, оттуда по ссылкам и т.д. По старой привычке храню не ссылки, а скачиваю документы, поэтому ссылками не поделюсь. Но найти не проблема.

У прямоугольников всегда все стороны параллельны

Это сообщение отредактировал(а) I_Am_Rock - 11.7.2011, 14:36

Если про эту задачу, то, когда я писал, параллельность задана не была.
Если вообще - то это, звиняюсь, как?

вроде как по вашему адресу
http://en.wikipedia.org/wiki/R-tree