Что такое попарное пересечение

Сколько точек пересечения могут иметь четыре попарно пересекающиеся прямые?

Сразу говорю, что задачу решать НЕ НАДО. Оставьте это мне. Я просто хочу разобраться, что означает «попарное пересекающиеся прямые».

У меня есть такая интерпретация: Имеется в виду, что все прямые «собраны» в пары. И каждая такая «сладкая парочка» пересекается другой такой же парой или «одиночной» прямой. Правда в этом конкретном случае «одиночек» нет, ибо количество прямых четное.

Я правильно все понимаю, или моя интерпретация неверна? Если неверна, то что тогда имеется в виду?

задан 23 Май ’13 13:26

I_Robot
183 ● 4 ● 17 ● 38
92&#037 принятых

Здесь имеется в виду, что какие бы две прямые из четырёх мы ни взяли, они будут пересекаться.

«они будут пересекаться.» Может быть, более точным будет сказать «они ДОЛЖНЫ пересекаться»?

Кстати, преобразуйте пожалуйста свой комментарий в ответ, дабы я мог закрыть вопрос.

3 ответа

Можно сказать «они пересекаются», «они должны пересекаться», «они будут пересекаться». Это всё одна и та же мысль. Суть в том, что любые две прямые из четырёх имеют точку пересечения. Фактически, это означает, что среди прямых нет параллельных (хотя в принципе такие прямые могли бы быть в какой-то другой ситуации, и тогда ответ был бы другим). Слово «попарно» вообще очень часто используется в математике. Например, «даны три попарно различных числа». Это значит, что первое число не равно второму, а также не равно третьему, а второе число не равно третьему.

отвечен 23 Май ’13 13:57

Если речь идет об одной паре прямых, то в одной точке, а ежели о двух парах и более, то рассматриваютя разные варианты расположения уже самих пересекающихся пар прямых.

отвечен 13 Сен ’15 13:02

Можете ли дать ссылку на определение «попарно пересекающиеся прямые» из учебника? Например как построить 5 попарно пересекающихся прямых? Можно-ли из этого сделать вывод, что одна прямая может пересекать лишь 2 других?

отвечен 22 Сен ’17 19:18

Здравствуйте

Источник

Как работает инструмент Парное пересечение

В этом разделе

Инструмент Парное пересечение (Pairwise Intersect) вычисляет пересечение между объектами двух векторных слоев или классов объектов, используя алгоритм парного сравнения объектов. Объекты или их часть, общие для обоих наборов (то есть, пересекающиеся), записываются в выходной класс объектов.

Сравнение инструментов Пересечение и Парное пересечение

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

Инструмент Пересечение (Intersect)

Вычисляются все перекрытия (пересечения) между всеми объектами, независимо от того, к какому входному слою они относятся. Поскольку вычисляются все пересечения, выходные данные, возможно, будут содержать намного больше объектов, чем сумма всех входных объектов. Могут возникнуть ситуации, когда входные данные вместе содержат десятки тысяч объектов, а выходные – сотни миллионов объектов. Это объясняется сложными наложениями объектов друг на друга.

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

Входной слой 1 содержит 10 перекрывающихся полигональных объектов, надписанных значением OID.

Входной слой 2 – один полигон, надписанный значением OID.

Выходные данные инструмента Пересечь: 167 выходных объектов, надписанных номерами OID.

Инструмент попарного пересечения

С помощью инструмента Парное пересечение создаются более простые выходные данные. Каждый выходной объект представляет собой пересечение одного объекта входного слоя 1 и объекта входного слоя 2. Инструмент Пересечение вычисляет пересечения объектов слоя 1, а инструмент Парное пересечение – нет.

Выходные данные инструмента Парное пересечение: 10 выходных объектов.

Входные полигоны и выходные точки

Выходные точечные объекты инструмента Пересечение находятся в местах пересечений вершин полигона первого слоя и границы полигона второго входного слоя.

Выходными точечными объектами инструмента Парное пересечение являются места касания вершин одного из векторных слоев и границы полигона другого векторного слоя. Точки пересечения полигонов не возвращаются.

Выходные точечные данные пересечения полигонов Выходные точечные данные парного пересечения полигонов

Основные различия

Производительность

Примечание:

Помните, что выходные данные этих инструментов значительно различаются. Поэкспериментируйте с небольшими поднаборами данных для анализа выходных данных и определения подходящего вам инструмента.

Инструмент Пересечение является более сложным и предназначен для поиска всех наложений между всеми входными объектами. Учитывая сложность таких операций, инструмент Пересечение является очень эффективным и масштабируемым средством. Если вам необходимо определить все места перекрытия между всеми входными объектами, инструмент Пересечение подойдет вам наилучшим образом.

Какой инструмент использовать?

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

Источник

Попарное пересечение множеств в Python

если у меня есть переменное количество наборов (назовем число n), которые в большинстве m элементы каждый, каков наиболее эффективный способ вычисления попарных пересечений для всех пар множеств? Обратите внимание, что это отличается от пересечения всех n наборы.

например, если у меня есть следующие наборы:

Я хочу иметь возможность найти:

другой приемлемый формат (если это делает вещи проще) будет карта элементов в данном наборе наборов, которые содержат тот же элемент. Например:

дополнительная справочная информация:

3 ответов

это должно делать то, что вы хотите

издеваться над некоторыми данными

создайте список индексов наборов в S, чтобы на наборы можно было ссылаться более кратко ниже

получить все возможные уникальные пары элементов в S; однако, поскольку пересечение множества коммутативно, мы хотим комбинации вместо перестановок

написать a функция выполняет заданное пересечение

сложите эту функцию над парами и введите результат от каждого вызова функции к ее аргументам

этот решение, действительно просто два строки кода: (i) вычислить перестановки; (ii) затем применить некоторую функцию над каждой перестановкой, сохраняя возвращаемое значение в структурированном контейнере (ключ-значение) контейнер

объем памяти этого решения минимален, но вы можете сделать еще лучше, вернув выражение генератора на последнем шаге, т. е.

обратите внимание, что при таком подходе, ни последовательность пар, ни соответствующих перекрестках были записаны в память—т. е. оба пар и res являются итераторами.

Если мы можем предположить, что входные наборы упорядочены, подход псевдо-mergesort кажется многообещающим. Рассматривая каждый набор как отсортированный поток, продвигайте потоки параллельно, всегда продвигая только те, где значение является самым низким среди всех текущих итераторов. Сравните каждое текущее значение с новым минимумом каждый раз, когда итератор расширен, и сбросьте совпадения в коллекции одного и того же элемента.

Источник

И. М. Смирнова, В. А. Смирнов

Главная > Документ

И.М.Смирнова, В.А.Смирнов

ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ ПО ГЕОМЕТРИИ

Обычно экстремальные задачи, или задачи на нахождение наибольших и наименьших значений, решаются в курсе алгебры и начал анализа старших классов с помощью производной.

Вместе с тем, имеется важный класс геометрических экстремальных задач, которые решаются своими методами без помощи производной.

Эти задачи, с одной стороны, имеют большое значение, как для математики, так и для ее приложений, а с другой стороны, развивают геометрические представления учащихся, формируют необходимые умения и навыки решения экстремальных задач, могут служить пропедевтикой изучения соответствующих разделов курса алгебры и начал анализа.

Особую роль при этом играет методика решения таких задач, при которой задачи разбиваются на подзадачи, посильные для самостоятельного решения учащихся.

Здесь мы рассмотрим экстремальные задачи, которые можно решать на уроках геометрии с учащимися 7-9 и 10-11 классов. Часть из них содержится в учебниках [7], [8].

Обратим внимание на то, что некоторые хорошо известные теоремы и задачи курса геометрии 7-9 классов можно рассматривать как экстремальные задачи.

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

Наименьшее расстояние от данной точки до точек данной окружности называется расстоянием от точки до окружности.

Задача 3. Среди всех точек данной окружности найти такие, расстояние от которых до данной прямой наибольшее и наименьшее, соответственно.

В качестве самостоятельной работы предлагаем следующую задачу.

Приведем несколько примеров экстремальных задач комбинаторного характера.

Задача 5. Какое наибольшее число точек попарных пересечений могут иметь n прямых?

Решение. Заметим, что наибольшее число точек попарных пересечений получается, если каждая прямая пересекается с каждой, и при этом никакие три прямые не пересекаются в одной точке. В этом случае каждая из n прямых имеет n – 1 точку пересечения с остальными прямыми. При этом, поскольку каждая точка пересечения принадлежит двум прямым, то общее число точек пересечения будет равно .

Задача 6. На какое наибольшее число частей могут разбивать плоскость n прямых?

Ответ. частей.

Задача 7. Какое наибольшее число точек самопересечения может иметь замкнутая ломаная с пятью сторонами?

Решение. Каждая сторона ломаной может пересекаться только с не соседними сторонами. Таких сторон у пятисторонней ломаной две. Значит, число точек самопересечения не превосходит Пример замкнутой пятисторонней ломаной с пятью точками самопересечения дает пентаграмма (рис. 4).

В качестве самостоятельной работы предлагаем следующие задачи

Задача 8. Какое наибольшее число точек попарных пересечений могут иметь n окружностей?

Задача 9. На какое наибольшее число частей могут разбивать плоскость n окружностей?

Задача 10. Какое наибольшее число точек самопересечения может иметь замкнутая ломаная с (2 n + 1)-ой стороной? Приведите пример для n = 3.

Ответ. (2 n + 1)( n – 1). Пример ломаной приведены на рисунке 5.

Решение. Допустим, что существует шесть точек внутри круга радиуса 1, попарные расстояния между которыми больше 1. Проведем из центра круга радиусы через каждую из этих точек. Ясно, что никакие две точки не могут лежать на одном радиусе. Тогда по крайней мере два из шести радиусов образуют угол, не превосходящий 60. Расстояния между любыми двумя точками на этих радиусах не может превосходить 1. Противоречие.

Задача 12. На шахматной доске с обычной раскраской нарисуйте окружность наибольшего возможного радиуса так, чтобы она не пересекала ни одного белого поля.

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

Задача 13. Каково наименьшее число кругов, которыми можно покрыть круг вдвое большего радиуса?

Решение. 7 кругов. Каждый маленький круг может покрыть дугу окружности большого круга, не большую чем 60. Поэтому для того, чтобы покрыть всю окружность большого круга потребуется не менее шести маленьких кругов. Для покрытия всего большого круга потребуется не менее семи кругов вдвое меньшего радиуса. На рисунке 7 приведен пример покрытия, состоящего ровно из семи кругов.

В качестве самостоятельной работы предлагаем следующие задачи.

Задача 16. На данной прямой найдите точку, из которой данная окружность видна под наибольшим углом.

Задача 17. На данной окружности найдите точку, из которой данный отрезок виден под наибольшим углом.

Рассмотрим теперь одну из классических экстремальных задач – задачу Герона, имеющую многочисленные приложения

В качестве самостоятельной работы учащимся можно предложить следующие задачи.

Задача 20. Постройте треугольник наименьшего периметра, если заданы две вершины и прямая, которой принадлежит третья вершина.

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

Рассмотрим вопрос о том, в каком случае существует решение этой и предыдущей задач.

Дело в том, что прямая C ’ C ” может не пересекать стороны угла. Выясним, в каких случаях это может происходить.

Если данный угол острый, то угол C ’ OC ” меньше развернутого и, следовательно, прямая C ’ C ” пересекает стороны угла и, значит, задача имеет решение.

В качестве самостоятельной работы предлагаем провести аналогичное исследование задачи 23.

Задача 25. В данный треугольник вписать треугольник наименьшего периметра.

Будем предполагать, что треугольник ABC остроугольный. Тогда такие точки будут существовать.

Эта задача может быть рассмотрена в восьмом классе при изучении темы «Замечательные точки в треугольнике». В качестве самостоятельной работы учащимся можно предложить доказать, что в случае прямоугольного или тупоугольного треугольника задача не имеет решения.

Задача 26. Какая наибольшая сторона может быть у правильного треугольника, помещающегося в единичном квадрате?

В качестве самостоятельной работы предлагаем следующие задачи.

Задача 27. В единичный квадрат впишите четырехугольник наименьшего периметра. Сколько решений имеет задача?

Ответ. Прямоугольники, стороны которых параллельны диагоналям квадрата. Бесконечно много.

Задача 28. Какая наибольшая сторона может быть у правильного шестиугольника, помещающегося в квадрате со стороной 1?

Ответ. (рис. 17).

Рассмотрим еще одну классическую задачу – задачу Штейнера, имеющую большое прикладное значение, связанное с прокладкой дорог, трубопроводов и т.д., соединяющих заданные пункты и имеющих наименьшую протяженность.

Задача 29. Для данного треугольника найдите точку, сумма расстояний от которой до вершин треугольника принимает наименьшее значение.

Источник