caa a22 4500 469075457 CHVBK 20180323132934.0 cr unu---uuuuu 170328e19920201xx s 000 0 eng 10.1007/BF02187831 doi (NATIONALLICENCE)springer-10.1007/BF02187831 Valtr Pavel Department of Applied Mathematics, Charles University, Malostranské nám. 25, 11800, Praha 1, Czechoslovakia aut Convex independent sets and 7-holes in restricted planar point sets [Elektronische Daten] [Pavel Valtr] For a finite setA of points in the plane, letq(A) denote the ratio of the maximum distance of any pair of points ofA to the minimum distance of any pair of points ofA. Fork>0 letc α(k) denote the largest integerc such that any setA ofk points in general position in the plane, satisfying % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrpepeei0xd9Wq-Jb9% vqaqFfpe0db9as0-LqLs-Jirpepeei0-bs0Fb9pgea0db9fr-xfr-x% frpeWZqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadghacaGGOa% GaamyqaiaacMcacqGH8aapiiaacqWFXoqydaGcaaqaaGqaciaa+Tga% aSqabaaaaa!3EAF! $$q(A)< \alpha \sqrt k $$ for fixed % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrpepeei0xd9Wq-Jb9% vqaqFfpe0db9as0-LqLs-Jirpepeei0-bs0Fb9pgea0db9fr-xfr-x% frpeWZqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaGGaaiab-f7aHj% abgwMiZoaakaaabaGae8NmaiZaaOaaaeaacqWFZaWmaSqabaacbiGc% caGFVaGae8hWdahaleqaaOGaeSiuIiKaaGymaiaac6cacaaIWaGaaG% ynaaaa!4406! $$\alpha \geqslant \sqrt {2\sqrt 3 /\pi } \doteq 1.05$$ , contains at leastc convex independent points. We determine the exact asymptotic behavior ofc α(k), proving that there are two positive constantsβ=β(α),γ such thatβk 1/3≤c α(k)≤γk 1/3. To establish the upper bound ofc α(k) we construct a set, which also solves (affirmatively) the problem of Alonet al. [1] about the existence of a setA ofk points in general position without a 7-hole (i.e., vertices of a convex 7-gon containing no other points fromA), satisfying % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrpepeei0xd9Wq-Jb9% vqaqFfpe0db9as0-LqLs-Jirpepeei0-bs0Fb9pgea0db9fr-xfr-x% frpeWZqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadghacaGGOa% GaamyqaiaacMcacqGH8aapiiaacqWFXoqydaGcaaqaaGqaciaa+Tga% aSqabaaaaa!3EAF! $$q(A)< \alpha \sqrt k $$ . The construction uses "Horton sets,” which generalize sets without 7-holes constructed by Horton and which have some interesting properties. Springer-Verlag New York Inc., 1992 Discrete & Computational Geometry Springer New York 7/2(1992-02-01), 135-152 0179-5376 7:2<135 1992 7 454 https://doi.org/10.1007/BF02187831 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02187831 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Valtr Pavel Department of Applied Mathematics, Charles University, Malostranské nám. 25, 11800, Praha 1, Czechoslovakia aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 7/2(1992-02-01), 135-152 0179-5376 7:2<135 1992 7 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence SWISSBIB 132096153 BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer