Cтраница 3
Книги JI3J - JI5J посвящены так называемой комбинаторной геометрии - разделу, родственному дискретной геометрии и находящемуся на стыке элементарной геометрии и теории выпуклых тел. Эти три книги практически не пересекаются по своему содержанию: в них излагаются разные разделы комбинаторной геометрии. [31]
Задачи этой главы подобраны и сгруппированы так, чтобы в ходе их решения последовательно разъяснялось содержание некоторых проблем комбинаторного анализа ( § § 1, 2, 4) и вырабатывались соответствующие навыки. Задачи же, составляющие содержание § 3, имеют целью систематическое введение в современную теорию матрои-дов и комбинаторных геометрий. [32]
Книга также содержит как дополнительные задачи по темам, отраженным в первой части, так и задачи по некоторым новым темам, затрагивающие более глубокие вопросы дифференциальной геометрии и топологии. Среди новых тем, представленных во второй части, следует отметить компьютерную геометрию и топологию, кинематику и геометрию, геометрические конструкции ( такие, как джеты, многообразия Штифеля и Грассмана и т.п.), производная Ли, задачи на упаковку, комбинаторная геометрия на плоскости и в пространстве, элементы гамильтоновой механики. [33]
Ее основные результаты, проблематика, методы появились именно в нашем столетни. Круг задач, относящихся к современной комбинаторной геометрии, весьма широк. Однако можно указать некоторую общую схему, в рамки которой укладывается значительная часть задач комбинаторной геометрии. [34]
Эта глава посвящена рассмотрению четырех тесно связанных между сабой задач комбинаторной геометрии. Стержнем главы является известная гипотеза Хадвигера [1] о том, что ограниченное выпуклое тело / ( может быть покрыто не более чем 2П телами, гомотетичными телу К с положительным коэффициентом гомотетии, меньшим единицы. В работе [2] введена еще одна задача комбинаторной геометрии - задача освещения. С, равно наименьшему числу освещающих пучков. В работах [3, 4] рассматриваются еще две задачи, близкие указанным. Оказалось [5], что для неограниченных выпуклых тел все четыре задачи р а з л и ч-н ы, хотя и тесно связаны. Кроме того, имеются отдельные результаты более частного характера. [35]
Она отличается от существующих книг по комбинаторной геометрии большим числом новых постановок зааач и полученных результатов. Использование различных пожиманий выпуклости позволяет по-пному осмыслить классическое теоремы комбинаторной геометрии, дает ряд новых результатов и формулировок проблем. [36]
Эта условность членения материала книги между отдельными циклами задач частично задевает даже книги [4] и [13], предшествующие настоящей, в которых также затронуты некоторые темы, которые были бы вполне уместны и в настоящей книге, - обстоятельство, о котором стоит, быть может, предупредить преподавателя, собирающегося использовать эту книгу в работе математического кружка. Непосредственно комбинаторной геометрии ( о ней говорится в Предисловии к книге) посвящены лишь два последних цикла задач, на которые хочется особо обратить внимание читателей. Однако и многие другие задачи - в первую очередь это относится, пожалуй, к циклам 2 и 3 - также навеяны комбинаторной геометрией. [37]
H, Boerdljk); однако это решение осталось не опубликованным, так что датировать решение этой задачи приходится 1962 г., когда была напечатана посвященная этой тематике статья [43] известных специалистов по комбинаторной геометрии Людвига Данцера и Бранко Грюнбаума. Грюнбауму решение задачи 31 б) немедленно переносится и на случай расположения п точек в - мерном ( евклидовом) пространстве1); напротив, по поводу Л - мерного аналога задачи 32 б) при k 4 можно лишь утверждать что соответствующее ( наибольшее возможное. [38]
При решении задач этого цикла следует иметь в виду определенное сковарство рассматриваемой в проблематики: здесь совсем простые по условию задачи сплошь и рядом оказываются весьма нелегкими, причем сложность двух, казалось бы, весьма схожих задач зачастую является совсем разной. Так, в то время как задача 25 г) является сравнительно простой, в точности аналогичная ей задача об оценке наибольшего из образованных п точками углов до сих пор не решена, хотя ее пытались решить многие известные математики; подобно этому из двух весьма близких по формулировке задач 32 и 34 ( ср. Поучительно также сопоставление задач 31 а) и 32 а) с их стереометрическими аналогами 31 б) и 32 б) ( или даже сравнение совсем простой задачи 33 а) с задачей 336)), иллюстрирующее типичное для комбинаторной геометрии резкое возрастание трудностей при переходе от планиметрических проблем к стереометрическим или многомерным ( ср. [39]
Она основана на описании геометрических объектов в терминах свойств конечных подмножеств. Например, некоторое множество выпукло тогда и только тогда, когда отрезок, определяемый любой парой его точек, лежит полностью в этом множестве. Неадекватность комбинаторной геометрии для нас заключается в том, что для большинства интересующих нас множеств число их конечных подмножеств бесконечно, а это препятствует их алгоритмической обработке. Работа последних лет в области геометрических алгоритмов направлена на избавление от этих недостатков и развитие математики, ведущей к созданию хороших алгоритмов. [40]
Прежде чем закончить этот раздел, отметим, что метод Грэхема явным образом использует сортировку. Аналогично тому, как исследование сортировки показало, что не существует одного алгоритма, лучшего во всех случаях, мы увидим, что то же самое справедливо и для задачи построения выпуклой оболочки. Давайте продолжим исследование комбинаторной геометрии в поисках идей, способных привести к иным алгоритмам построения выпуклой оболочки. [41]
Ее основные результаты, проблематика, методы появились именно в нашем столетни. Круг задач, относящихся к современной комбинаторной геометрии, весьма широк. Однако можно указать некоторую общую схему, в рамки которой укладывается значительная часть задач комбинаторной геометрии. [42]
Книга имеет форму задачника с указаниями и подробными решениями. Все сведения, необходимые для понимания задач, изложены в тексте книги. Многие из собранных здесь задач предлагались участникам московских школьных математических кружков и олимпиад. Некоторые из задач заимствованы из серьезных научных работ, относящихся к новому раз делу математики - комбинаторной геометрии. [43]