Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949122 | Computational Geometry | 2017 | 10 Pages |
Abstract
In 1978 ErdÅs asked if every sufficiently large set of points in general position in the plane contains the vertices of a convex k-gon, with the additional property that no other point of the set lies in its interior. Shortly after, Horton provided a construction-which is now called the Horton set-with no such 7-gon. In this paper we show that the Horton set of n points can be realized with integer coordinates of absolute value at most 12n12logâ¡(n/2). We also show that any set of points with integer coordinates combinatorially equivalent (with the same order type) to the Horton set contains a point with a coordinate of absolute value at least câ
n124logâ¡(n/2), where c is a positive constant.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Luis Barba, Frank Duque, Ruy Fabila-Monroy, Carlos Hidalgo-Toscano,