Property Testing for Point Sets on the Plane
| Autor: | Jie Han, Yoshiharu Kohayakawa, Marcelo Tadeu Sales, Henrique Stagni |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | LATIN 2018: Theoretical Informatics ISBN: 9783319774039 LATIN |
| DOI: | 10.1007/978-3-319-77404-6_43 |
| Popis: | A configuration is a point set on the plane, with no three points collinear. Given three non-collinear points p, q and \(r\in \mathbb {R}^2\), let \(\chi (p,q,r)\in \{-1,1\}\), with \(\chi (p,q,r)=1\) if and only if, when we traverse the circle defined by those points in the counterclockwise direction, we encounter the points in the cyclic order \(p,q,r,p,q,r,\dots \). For simplicity, extend \(\chi \) by setting \(\chi (p,q,r)=0\) if p, q and r are not pairwise distinct. Two configurations A and \(B\subset \mathbb {R}^2\) are said to have the same order type if there is a bijection \(\iota :A\rightarrow B\) such that \(\chi (p,q,r)=\chi (\iota (p),\iota (q),\iota (r))\) for all \((p,q,r)\in A^3\). We say that a configuration C contains a copy of a configuration A if there is \(B\subset C\) with A and B of the same order type. Given a configuration F, let \(\mathrm{Forb}(F)\) be the set of configurations that do not contain a copy of F. The distance between two configurations A and B with \(|A|=|B|=n\) is given by |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|