## Abstract

A configuration is a point set on the plane, with no three points collinear. Given three non-collinear points p, q and r∈ ℝ^{2}, let χ(p, q, r) ∈ { - 1, 1 }, with χ(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, ⋯. For simplicity, extend χ by setting χ(p, q, r) = 0 if p, q and r are not pairwise distinct. Two configurations A and B⊂ ℝ^{2} are said to have the same order type if there is a bijection ι: A→ B such that χ(p, q, r) = χ(ι(p), ι(q), ι(r)) for all (p, q, r) ∈ A^{3}. We say that a configuration C contains a copy of a configuration A if there is B⊂ C with A and B of the same order type. Given a configuration F, let 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 (Formula presented), where the minimum is taken over all bijections ι: A→ B. Roughly speaking, we prove the following property testing result: being free of a given configuration is efficiently testable. Our result also holds in the general case of hereditary properties P= Forb (F), defined by possibly infinite families F of forbidden configurations. Our results complement previous results by Czumaj, Sohler and Ziegler and others, in that we use a different notion of distance between configurations. Our proofs are heavily inspired on recent work of Fox and Wei on testing permutations and also make use of the regularity lemma for semi-algebraic hypergraphs of Fox, Pach and Suk. An extremal function involving order types, which may be of independent interest, plays an important rôle in our arguments.

Original language | English |
---|---|

Title of host publication | LATIN 2018 |

Subtitle of host publication | Theoretical Informatics - 13th Latin American Symposium, Proceedings |

Editors | Miguel A. Mosteiro, Michael A. Bender, Martin Farach-Colton |

Publisher | Springer Verlag |

Pages | 584-596 |

Number of pages | 13 |

ISBN (Print) | 9783319774039 |

DOIs | |

Publication status | Published - 2018 |

Externally published | Yes |

Event | 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 - Buenos Aires, Argentina Duration: 16 Apr 2018 → 19 Apr 2018 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10807 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 |
---|---|

Country/Territory | Argentina |

City | Buenos Aires |

Period | 16/04/18 → 19/04/18 |