Property Testing for Point Sets on the Plane

Autor(es)

Han, Jie ; Kohayakawa, Yoshiharu ; Sales, Marcelo Tadeu ; Stagni, Henrique ; Bender, MA ; FarachColton, M ; Mosteiro, MA

• Tipo de documento: Artigo Científico
• Fonte: LATIN 2018: THEORETICAL INFORMATICS; v. 10807, p. 13-pg., 2018-01-01.

Resumo

A configuration is a point set on the plane, with no three points collinear. Given three non-collinear points p, q and r is an element of R-2, let.(p, q, r) is an element of{-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 chi by setting chi(p, q, r) = 0 if p, q and r are not pairwise distinct. Two configurations A and B subset of R-2 are said to have the same order type if there is a bijection iota : A -> B such that chi(p, q, r) = chi (iota(p), iota(q), iota(r)) for all (p, q, r)is an element of A(3). We say that a configuration C contains a copy of a configuration A if there is B subset of 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 vertical bar A vertical bar = vertical bar B vertical bar = n is given by dist(A, B) = min(iota)1/2n(3) Sigma((p,q,r)is an element of A3 ')chi(p,q,r) - chi(iota(p), iota(q), iota(r))vertical bar, where the minimum is taken over all bijections iota : 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 role in our arguments. (AU)

• Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
• Beneficiário: Oswaldo Baffa Filho
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 15/15986-4 - Combinatória Assintótica com Aplicações em Teste de Propriedades e Estimação de Parâmetros.
• Beneficiário: Henrique Stagni
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 14/18641-5 - Circuitos hamiltonianos e problemas de ladrilhamento em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático