Конфигурационное пространство Кэли

В математической теории структурной жесткости конфигурационное пространство Кэли сцепления . над множеством его неребер $F$ , называемые параметрами Кэли, представляют собой набор расстояний, достигаемых $F$ во всех его рамках , под некоторыми $l_{p}$ -норма . Другими словами, каждая структура связи предписывает уникальный набор расстояний до неграниц. $G$ , поэтому набор всех каркасов можно описать набором расстояний, достигнутых любым подмножеством этих не-ребер. Обратите внимание, что это описание не может быть биекцией . Мотивацией использования параметров расстояния является определение непрерывного квадратичного разветвленного покрытия из конфигурационного пространства связи в более простое, часто выпуклое пространство. Следовательно, получение каркаса из конфигурационного пространства Кэли связи над некоторым набором неребер часто является вопросом решения квадратных уравнений.

Конфигурационные пространства Кэли тесно связаны с уплощаемостью и комбинаторной жесткостью графов.

Определения

Конфигурационное пространство Кэли

Определение через связи. ^{[ 1 ]} Рассмотрим связь $(G,\delta )$ , с графиком $G$ и $l_{p}^{p}$ -вектор длины ребра $\delta$ (т.е. $l_{p}$ -расстояния, поднятые до $p^{th}$ власть, для некоторых $l_{p}$ -норма) и набор неребер $F$ из $G$ . Конфигурационное пространство Кэли $(G,\delta )$ над $F$ в $\mathbb {R} ^{d}$ под для некоторых $l_{p}$ -норма, обозначаемая $\Phi _{F,l_{p}}^{d}(G,\delta _{G})$ , представляет собой набор $l_{p}^{p}$ -векторы расстояний $\delta _{F}$ достигается за счет неребер $F$ во всех рамках $(G,\delta )$ в $\mathbb {R} ^{d}$ . При наличии неравенства $l_{p}^{p}$ - ограничения по расстоянию , т.е. интервал $[\delta _{l},\delta _{r}]$ , конфигурационное пространство Кэли $\Phi _{F,l_{p}}^{d}\left(G,[\delta _{G}^{l},\delta _{G}^{r}]\right)$ определяется аналогично. Другими словами, $\Phi _{F,l_{p}}^{d}(G,\delta _{G})$ — проекция полуалгебраического множества Кэли-Менгера с фиксированным $(G,\delta )$ или $\left(G,[\delta _{G}^{l},\delta _{G}^{r}]\right)$ , на нерёбра $F$ , называемые параметрами Кэли.

Определение через проекции конуса расстояний. ^{[ 2 ]} Рассмотрим конус $\Phi _{n,l_{p}}$ векторов попарных $l_{p}^{p}$ -расстояния между $n$ точки. Также рассмотрите $d$ -слой этого конуса $\Phi _{n,l_{p}}^{d}$ , т. е. подмножество векторов $l_{p}^{p}$ -расстояния между $n$ указывает на $\mathbb {R} ^{d}$ . Для любого графика $G$ , рассмотрим проекцию $\Phi _{G,l_{p}}^{d}$ из $\Phi _{n,l_{p}}^{d}$ на края $G$ , т. е. множество всех векторов $\delta _{G}$ из $l_{p}^{p}$ -расстояния, на которых осуществляется связь $(G,\delta _{G})$ имеет структуру в $\mathbb {R} ^{d}$ . Далее для любой точки $\delta _{G}$ в $\Phi _{G,l_{p}}^{d}$ и любой набор нерёбер $F$ из $G$ , волокно рассмотрим $\delta _{G}$ в $\Phi _{n,l_{p}}^{d}$ по координатам $F$ , т. е. набор векторов $\delta _{G\cup F}$ из $l_{p}^{p}$ -расстояния, на которых осуществляется связь $(G\cup F,\delta _{G\cup F})$ имеет структуру в $\mathbb {R} ^{d}$ .

Конфигурационное пространство Кэли $\Phi _{F,l_{p}}^{d}(G,\delta _{G})$ есть проекция этого слоя на множество неребер $F$ , то есть набор $l_{p}^{p}$ -расстояния, достигнутые неребрами в $F$ во всех рамках $(G,\delta _{G})$ в $\mathbb {R} ^{d}$ . ^{[ 2 ]} При наличии неравенства $l_{p}^{p}$ -ограничения по расстоянию, т. е. интервал $[\delta _{l,G},\delta _{r,G}]$ , конфигурационное пространство Кэли $\Phi _{F,l_{p}}^{d}(G,[\delta _{l,G},\delta _{r,G}])$ - это проекция набора слоев на множество неребер $F$ .

Определение через ветвящиеся оболочки. Пространство конфигурации Кэли связи в $\mathbb {R} ^{d}$ — базовое пространство ветвящегося покрытия, общий объем которого является конфигурационным пространством связи в $\mathbb {R} ^{d}$ .

Ориентированное конфигурационное пространство Кэли

Для 1-мерного древовидного графа $G$ с основанием без края $f$ , каждая точка каркаса связи $(G,\delta )$ в $\mathbb {R} ^{d}$ под $l_{2}$ -норму можно размещать итеративно в соответствии с вектором ориентации $\sigma$ , также называемый типом реализации. Записи $\sigma$ — локальные ориентации троек точек для всех шагов построения каркаса. А $\sigma$ -ориентированное конфигурационное пространство Кэли $(G,\delta )$ над $f$ , обозначенный $\Phi _{f,\sigma }^{2}(G,\delta )$ — конфигурационное пространство Кэли $(G,\delta )$ над $f$ ограничивается рамками, соблюдающими $\sigma$ . ^{[ 3 ]} Другими словами, для любого значения $f$ в $\Phi _{f,\sigma }^{2}(G,\delta )$ , соответствующий каркасам $(G,\delta )$ уважать $\sigma$ и являются подмножеством фреймворков в $\Phi _{f}^{2}(G,\delta )$ .

Минимальный полный вектор Кэли

Для 1-мерного древовидного графа $G=(V,E)$ с низкой сложностью Кэли на базе без края $f$ , минимальный вектор Кэли $F$ это список $O(|V|)$ не края $G$ такой, что график $G\cup F$ в целом является глобально жестким . ^{[ 4 ]}^{[ 5 ]}

Характеристики

Свойство одного интервала

Пара $(G,f)$ , состоящий из графа $G$ и без края $f$ , имеет свойство единственного интервала в $\mathbb {R} ^{d}$ под каким-то $l_{p}$ -норма, если для каждой связи $(G,\delta )$ , конфигурационное пространство Кэли $\Phi _{f,l_{p}}^{d}(G,\delta )$ представляет собой одиночный интервал. ^{[ 1 ]}

Присущая выпуклость

График $G$ имеет собственное выпуклое конфигурационное пространство Кэли в $\mathbb {R} ^{d}$ под каким-то $l_{p}$ нормой, если для любого разбиения ребер $G$ в $H$ и $F$ и каждая связь $(H,\delta )$ , конфигурационное пространство Кэли $\Phi _{F,l_{p}}^{d}(H,\delta )$ является выпуклым. ^{[ 1 ]}

Генеричность по выпуклости

Позволять $G=(V,E)$ быть графиком и $F$ быть непустым множеством неребер $G$ . Также пусть $r$ быть основой в $\mathbb {R} ^{d}$ любой связи, граф ограничений которой $G$ и рассмотрим соответствующее $l_{p}^{p}$ -вектор длины ребра $\delta _{r}$ в конусе $\Phi _{n,l_{p}}$ , где $n=|V|$ . Как определено в Ситхараме и Уиллоуби, ^{[ 2 ]} рамки $r$ является общим относительно свойства выпуклых конфигурационных пространств Кэли, если

Есть открытый район $\Omega$ из $\delta _{r}$ в $d$ -слой $\Phi _{n,l_{p}}^{d}$ (соответствует окрестностям вокруг $r$ рамок в $\mathbb {R} ^{d}$ ); и
$\Phi _{F,l_{p}}^{d}(G,\delta _{r})$ выпукло тогда и только тогда, когда для всех $\delta _{q}\in \Omega$ , $\Phi _{F,l_{p}}^{d}(G,\delta _{q})$ является выпуклым.

Теорема. ^{[ 2 ]} Каждая общая структура графа $G$ в $\mathbb {R} ^{d}$ имеет выпуклое конфигурационное пространство Кэли над множеством неребер $F$ тогда и только тогда, когда каждая связь $(G,\delta )$ делает.

Теорема. ^{[ 2 ]} Выпуклость конфигурационных пространств Кэли не является общим свойством каркасов.

Доказательство. Рассмотрим график на рисунке 1. Также рассмотрим структуру $p$ в $\mathbb {R} ^{2}$ чьи попарно $l_{2}$ -вектор расстояния $\delta _{p}$ присваивает расстояние 3 немаркированным краям, 4 — $x$ и от 1 до $y$ и двумерная структура $q$ чьи попарно $l_{2}$ -вектор расстояния $\delta _{q}$ присваивает расстояние 3 немаркированным краям, 4 — $x$ , и 4 до $y$ . Конфигурационное пространство Кэли $\Phi _{f}^{2}(G,\delta _{p})$ состоит из 2 интервалов: один интервал представляет собой каркасы с вершиной $B$ на правой стороне линии, определяемой вершинами $C$ и $D$ а другой интервал представляет собой каркасы с вершиной $B$ на левой стороне этой линии. Интервалы не пересекаются из-за неравенства треугольника, индуцированного расстояниями, присвоенными ребрам. $x$ и $y$ . Более того, $p$ является общей структурой относительно выпуклых конфигурационных пространств Кэли над $f$ в $\mathbb {R} ^{2}$ : вокруг есть соседство фреймворков $p$ чьи пространства конфигурации Кэли $\Phi _{f}^{2}(G,\delta )$ это 2 интервала.

С другой стороны, конфигурационное пространство Кэли $\Phi _{f}^{2}(G,\delta _{q})$ представляет собой один интервал: неравенства треугольника, индуцированные четырехугольником, содержащим $f$ определить один интервал, который содержится в интервале, определяемом неравенствами треугольника, индуцированными расстояниями, присвоенными краям $x$ и $y$ . Более того, $q$ является общей структурой относительно выпуклых конфигурационных пространств Кэли над $f$ в $\mathbb {R} ^{2}$ : вокруг есть соседство фреймворков $q$ чьи пространства конфигурации Кэли превышают $f$ в $\mathbb {R} ^{2}$ представляют собой один интервал. Таким образом, одна общая структура имеет выпуклое конфигурационное пространство Кэли, а другая — нет.

Общая полнота

В целом полное или просто полное пространство конфигурации Кэли представляет собой конфигурацию Кэли связи. $(G,\delta )$ над набором неребер $F$ такая, что каждая точка в этом пространстве в общем случае соответствует конечному числу каркасов $(G,\delta )$ и пространство имеет полную меру . ^{[ 1 ]} Эквивалентно, график $G\cup F$ в общем случае является минимально-жестким . ^{[ 1 ]}

Результаты для евклидовой нормы

Следующие результаты относятся к конфигурационным пространствам Кэли связей над неребрами при $l_{2}$ -норма, также называемая евклидовой нормой .

Теоремы об одном интервале

Позволять $G$ быть графиком. Рассмотрим 2 суммы разложение на $G$ , т. е. рекурсивно разлагая $G$ на его 2-суммные компоненты. Минимальные элементы этого разложения называются минимальными компонентами 2-суммы $G$ .

Теорема. ^{[ 1 ]} Для $d\leq 2$ , пара $(G,f)$ , состоящий из графа $G$ и без края $f$ , имеет свойство единственного интервала в $\mathbb {R} ^{d}$ тогда и только тогда, когда все минимальные компоненты 2-суммы $G\cup f$ которые содержат $f$ являются частичными 2-деревьями .

Последнее условие эквивалентно требованию, чтобы все минимальные компоненты 2-суммы $G\cup f$ которые содержат $f$ являются 2-сглаживаемыми , поскольку частичные 2-деревья представляют собой в точности класс 2-сглаживаемых графов (см. результаты о 2-сглаживаемости ). Этот результат не обобщается для размерностей $d\geq 3$ . ^{[ 1 ]} Запрещенные миноры для 3-сглаживаемости представляют собой полный граф. $K_{5}$ и 1-скелет октаэдра $K_{2,2,2}$ (см. результаты по 3-уплощенности ). На рисунке 2 показаны противоположные примеры для $d=3$ . Обозначим график слева через $G$ и график справа от $H$ . Обе пары $(G,f)$ и $(H,f)$ иметь свойство единственного интервала в $\mathbb {R} ^{3}$ : вершины $f$ может вращаться в 3-х измерениях вокруг плоскости. Кроме того, оба $G\cup f$ и $H\cup f$ сами являются минимальными компонентами двухсуммы, содержащими $f$ . Однако ни $G\cup f$ ни $H\cup f$ является 3-сплющенным: сжимающимся $f$ в $G\cup f$ урожайность $K_{5}$ и заключение контрактов $f$ в $H\cup f$ урожайность $K_{2,2,2}$ .

Пример. Рассмотрим график $G$ на рисунке 3, чьи неребра являются $d_{1}$ и $d_{2}$ . График $G$ является собственным и единственным минимальным компонентом 2-суммы, содержащим любое неребро. Кроме того, график $G\cup d_{1}\cup d_{2}$ является 2-деревом, поэтому $G$ является частичным 2-деревом. Следовательно, по теореме выше обе пары $(G,d_{1})$ и $(G,d_{2})$ иметь свойство единственного интервала в $\mathbb {R} ^{2}$ .

Следующая гипотеза характеризует пары $(G,f)$ со свойством одиночного интервала в $\mathbb {R} ^{d}$ для произвольного $d$ .

Гипотеза. ^{[ 1 ]} Пара $(G,f)$ , состоящий из графа $G$ и без края $f$ , имеет свойство единственного интервала в $\mathbb {R} ^{d}$ тогда и только тогда, когда для любой минимальной компоненты 2-суммы $G\cup f$ который содержит $f$ и это не $d$ -сплющенный, $f$ должны быть удалены, продублированы или заключены контракты для получения запрещенного несовершеннолетнего для $d$ -сплющиваемость от $G$ .

1-степени разложимых по дереву связей в R ²

Следующие результаты касаются ориентированных конфигурационных пространств Кэли одномерных древовидных связей над некоторым базовым неребром в $\mathbb {R} ^{2}$ . Обратитесь к разлагаемым по дереву графам для определения общих связей, используемых ниже.

Теорема. ^{[ 3 ]} Для общей разложимой по дереву связи с 1 степенями свободы $(G,\delta )$ с основанием без края $f$ имеют место следующие:

Ориентированное конфигурационное пространство Кэли $\Phi _{f,\sigma }^{2}(G,\delta )$ представляет собой совокупность непересекающихся замкнутых вещественных интервалов или пустую;
Любая конечная точка этих замкнутых интервалов соответствует длине $f$ в рамках крайней увязки; и
Для любой вершины $v$ или любой некраевой $g$ из $G$ , карты из $\Phi _{f,\sigma }^{2}(G,\delta )$ к координатам $v$ или длина $g$ в рамках $(G,\delta )$ являются непрерывными функциями на каждом из этих отрезков.

Эта теорема дает алгоритм для вычисления (ориентированных) конфигурационных пространств Кэли одномерных древовидных связей над базовым неребром путем простого построения ориентированных каркасов всех крайних связей. ^{[ 3 ]}^{[ 4 ]} Этот алгоритм может потребовать времени, экспоненциально зависящего от размера связи и выходного пространства конфигурации Кэли. Для 1-мерного древовидного графа $G$ , три меры сложности его ориентированных конфигурационных пространств Кэли: ^{[ 4 ]}

Размер Кэли: максимальное количество непересекающихся замкнутых реальных интервалов в пространстве конфигурации Кэли по всем связям. $(G,\delta )$ ;
Вычислительная сложность Кэли: максимальная временная сложность для получения этих интервалов по всем связям. $(G,\delta )$ ; и
Алгебраическая сложность Кэли: максимальная алгебраическая сложность описания каждой конечной точки этих интервалов по всем связям. $(G,\delta )$ .

Границы этих мер сложности даны у Ситхарама, Ванга и Гао. ^{[ 4 ]}^{[ 5 ]} Другой алгоритм вычисления этих ориентированных конфигурационных пространств Кэли обеспечивает линейную сложность Кэли в зависимости от размера базового графа. ^{[ 4 ]}

Теорема. ^{[ 4 ]}^{[ 6 ]} Для общей разложимой по дереву связи с 1 степенями свободы $(G,\delta )$ , где график $G$ имеет низкую сложность Кэли на базе без края $f$ , имеют место следующие утверждения:

Между любыми двумя каркасами существует не более двух непрерывных путей движения. $(G,\delta )$ ${\ displaystyle (G, \ delta)}$ ,
- и временная сложность поиска такого пути, если он существует, линейна по числу конечных точек интервала ориентированного конфигурационного пространства Кэли над $f$ что путь содержит; и
Существует алгоритм, формирующий всю совокупность связных компонент конфигурационного пространства каркасов $(G,\delta )$ ${\ displaystyle (G, \ delta)}$ ,
- и временная сложность генерации каждого такого компонента линейно зависит от количества конечных точек интервала ориентированного конфигурационного пространства Кэли по $f$ что содержит компонент.

Алгоритм приведен в Ситхараме, Ванге и Гао. ^{[ 4 ]} найти эти траектории движения. Идея состоит в том, чтобы начать с одной структуры, расположенной в одном интервале конфигурационного пространства Кэли, пройти вдоль этого интервала до его конечной точки и перейти к другому интервалу, повторяя эти два последних шага до тех пор, пока не будет достигнута целевая структура. Этот алгоритм использует следующие факты: (i) существует непрерывный путь движения между любыми двумя каркасами в одном и том же интервале, (ii) крайние связи существуют только в конечных точках интервала и (iii) во время движения низкая Кэли связь сложности меняет тип реализации только при переходе на новый интервал, и ровно одна локальная ориентация меняет знак во время этого перехода.

Пример. На рисунке 4 показана ориентированная структура одномерной древовидной разложимой связи с базовым нереберным соединением. $(v_{0},v'_{0})$ , расположенный в интервале конфигурационного пространства Кэли, и две другие структуры, ориентация которых вот-вот изменится. Вершины, соответствующие шагам построения, помечены в порядке построения. Более конкретно, первая структура имеет тип реализации $(1,-1,-1,1)$ . Ко второму каркасу существует непрерывный путь движения, имеющий тип реализации $(0,-1,-1,1)$ . Следовательно, эта структура соответствует конечной точке интервала, и переход к новому интервалу приводит к типу реализации $(-1,-1,-1,1)$ . Аналогично, третья структура соответствует конечной точке интервала с типом реализации $(-1,-1,0,1)$ и переход на новый интервал приводит к типу реализации $(-1,-1,1,1)$ .

Теорема. ^{[ 4 ]}^{[ 6 ]} (1) Для общей разложимой в дереве связи с 1 путем и 1 степенями свободы $(G,\delta )$ с низкой сложностью Кэли существует биективное соответствие между множеством фреймворков $(G,\delta )$ и точки на двумерной кривой, точки которых являются минимальными полными векторами расстояния Кэли. (2) Для типичной древовидно разложимой связи с 1 степенями свободы $(G,\delta )$ с низкой сложностью Кэли существует биективное соответствие между множеством фреймворков $(G,\delta )$ и указывает на $n$ -мерная кривая, точками которой являются минимальные полные векторы расстояния Кэли, где $n$ количество вершин последнего уровня графа $G$ .

Результаты для общих p -норм

Эти результаты распространяются на общие $l_{p}$ -норм.

Теорема. ^{[ 2 ]} Для общего $l_{p}$ -нормы, график $G$ имеет собственное выпуклое конфигурационное пространство Кэли в $\mathbb {R} ^{d}$ тогда и только тогда, когда $G$ является $d$ -сплющенный.

Направление «только если» было доказано в Ситхараме и Гао. ^{[ 1 ]} используя тот факт, что $l_{2}^{2}$ конус расстояния $\Phi _{n,l_{2}}$ является выпуклым. Как прямое следствие, $d$ -сглаживаемые графы и графы с присущими им выпуклыми конфигурационными пространствами Кэли в $\mathbb {R} ^{d}$ имеют одинаковые запрещенные второстепенные характеристики. Результаты по этим характеристикам см. в разделе «Уплощение графов» , а также более подробное обсуждение связи между конфигурационными пространствами Кэли и уплощаемостью.

Пример. Рассмотрим граф на рисунке 3, в котором оба неребра добавлены в качестве ребер. Полученный граф представляет собой 2-дерево, которое является 2-сглаживаемым при $l_{1}$ и $l_{2}$ нормы см. Уплощение графов . Следовательно, приведенная выше теорема указывает на то, что граф имеет собственное выпуклое конфигурационное пространство Кэли в $\mathbb {R} ^{2}$ под $l_{1}$ и $l_{2}$ нормы. В частности, конфигурационное пространство Кэли над одним или обоими неребрами $d_{1}$ и $d_{2}$ является выпуклым.

Приложения

Алгоритм EASAL ^{[ 7 ]} использует методы, разработанные в Ситхараме и Гао. ^{[ 1 ]} для работы с выпуклыми пространствами конфигурации Кэли для описания размерной, топологической и геометрической структуры евклидовых конфигурационных пространств в $\mathbb {R} ^{3}$ . Точнее, для двух наборов $n$ очки $A$ и $B$ в $\mathbb {R} ^{3}$ с ограничениями на интервальное расстояние между парами точек, поступающими из разных наборов, EASAL выводит все структуры этой связи так, что ни одна пара ограниченных точек не находится слишком близко друг к другу и по крайней мере одна пара ограниченных точек не находится достаточно близко друг к другу. Этот алгоритм имеет применение в молекулярной самосборке .

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Ситхарам, Мира; Гао, Хэпин (01 апреля 2010 г.). «Характеристика графов с выпуклыми и связными пространствами конфигурации Кэли» . Дискретная и вычислительная геометрия . 43 (3): 594–625. дои : 10.1007/s00454-009-9160-8 . ISSN 1432-0444 . S2CID 35819450 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Ситхарам, Мира; Уиллоуби, Джоэл (2015). Ботана, Франциско; Куарежма, Педро (ред.). «О уплощаемости графов» . Автоматизированный вывод по геометрии . Конспекты лекций по информатике. 9201 . Чам: Springer International Publishing: 129–148. arXiv : 1503.01489 . дои : 10.1007/978-3-319-21362-0_9 . ISBN 978-3-319-21362-0 . S2CID 23208 .
^ Jump up to: ^а ^б ^с Гао, Хэпин; Ситхарам, Мира (8 марта 2009 г.). «Характеристика одностепенных графов Хеннеберга-I с эффективными конфигурационными пространствами» . Материалы симпозиума ACM по прикладным вычислениям 2009 года . САК '09. Гонолулу, Гавайи: Ассоциация вычислительной техники. стр. 1122–1126. дои : 10.1145/1529282.1529529 . ISBN 978-1-60558-166-8 . S2CID 14117144 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Ситхарам, Мира; Ван, Мэнхан; Гао, Хэпин (2011). «Пространства конфигурации Кэли двумерных механизмов, часть I: крайние точки, пути непрерывного движения и минимальные представления». Препринт . arXiv : 1112.6008 .
^ Jump up to: ^а ^б Ситхарам, Мира; Ван, Мэнхан; Гао, Хэпин (2011). «Пространства конфигурации Кэли одномерных древовидных связей, часть II: комбинаторная характеристика сложности». Препринт . arXiv : 1112.6009 .
^ Jump up to: ^а ^б Ситхарам, Мира; Ван, Мэнхан (01 января 2014 г.). «Как на самом деле движется Чудовище: анализ Кэли пространств реализации механизмов с использованием CayMos» . Компьютерное проектирование . 46 : 205–210. дои : 10.1016/j.cad.2013.08.033 . ISSN 0010-4485 .
^ Озкан, Айсегуль; Прабху, Рахул; Бейкер, Трой; Пенс, Джеймс; Петерс, Йорг; Ситхарам, Мира (26 июля 2018 г.). «Алгоритм 990: эффективный атлас и поиск конфигурационных пространств наборов точек, ограниченных интервалами расстояний» . Транзакции ACM в математическом программном обеспечении . 44 (4): 48:1–48:30. дои : 10.1145/3204472 . ISSN 0098-3500 . S2CID 29156131 .

[:0-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Ситхарам, Мира; Гао, Хэпин (01 апреля 2010 г.). «Характеристика графов с выпуклыми и связными пространствами конфигурации Кэли» . Дискретная и вычислительная геометрия . 43 (3): 594–625. дои : 10.1007/s00454-009-9160-8 . ISSN 1432-0444 . S2CID 35819450 .

[:1-2] Jump up to: ^а ^б ^с ^д ^и ^ж Ситхарам, Мира; Уиллоуби, Джоэл (2015). Ботана, Франциско; Куарежма, Педро (ред.). «О уплощаемости графов» . Автоматизированный вывод по геометрии . Конспекты лекций по информатике. 9201 . Чам: Springer International Publishing: 129–148. arXiv : 1503.01489 . дои : 10.1007/978-3-319-21362-0_9 . ISBN 978-3-319-21362-0 . S2CID 23208 .

[:2-3] Jump up to: ^а ^б ^с Гао, Хэпин; Ситхарам, Мира (8 марта 2009 г.). «Характеристика одностепенных графов Хеннеберга-I с эффективными конфигурационными пространствами» . Материалы симпозиума ACM по прикладным вычислениям 2009 года . САК '09. Гонолулу, Гавайи: Ассоциация вычислительной техники. стр. 1122–1126. дои : 10.1145/1529282.1529529 . ISBN 978-1-60558-166-8 . S2CID 14117144 .

[:3-4] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Ситхарам, Мира; Ван, Мэнхан; Гао, Хэпин (2011). «Пространства конфигурации Кэли двумерных механизмов, часть I: крайние точки, пути непрерывного движения и минимальные представления». Препринт . arXiv : 1112.6008 .

[:4-5] Jump up to: ^а ^б Ситхарам, Мира; Ван, Мэнхан; Гао, Хэпин (2011). «Пространства конфигурации Кэли одномерных древовидных связей, часть II: комбинаторная характеристика сложности». Препринт . arXiv : 1112.6009 .

[:5-6] Jump up to: ^а ^б Ситхарам, Мира; Ван, Мэнхан (01 января 2014 г.). «Как на самом деле движется Чудовище: анализ Кэли пространств реализации механизмов с использованием CayMos» . Компьютерное проектирование . 46 : 205–210. дои : 10.1016/j.cad.2013.08.033 . ISSN 0010-4485 .

[7] Озкан, Айсегуль; Прабху, Рахул; Бейкер, Трой; Пенс, Джеймс; Петерс, Йорг; Ситхарам, Мира (26 июля 2018 г.). «Алгоритм 990: эффективный атлас и поиск конфигурационных пространств наборов точек, ограниченных интервалами расстояний» . Транзакции ACM в математическом программном обеспечении . 44 (4): 48:1–48:30. дои : 10.1145/3204472 . ISSN 0098-3500 . S2CID 29156131 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

Определения