CHCarlos Hidalgo-Toscano
Carlos Hidalgo-Toscano
*This is an algorithmically generated author record based on publicly available information.
Research Subjects
Carlos Hidalgo-Toscano has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
- Ruy Fabila-Monroy
Departamento de Matemáticas, CINVESTAV, Ciudad de México, Mexico
11 shared publications - Birgit Vogtenhuber
Graz University of Technology
3 shared publications Frank Duque
3 shared publications- Clemens Huemer
Universitat Politecnica de Catalunya
2 shared publications - César Hernández-Vélez
Facultad de Ciencias UASLP, Mexico
2 shared publications - Daniel Perz
University of Perugia
2 shared publications
Latest Publications
- Open Access
- 23 May 2024
- Published by Springer Nature in Acta Mathematica Hungarica
- Vol. 173 (1) , 1-22
No selection lemma for empty triangles
- 23 May 2024
- Published by Springer Nature in Acta Mathematica Hungarica
- Vol. 173 (1) , 1-22
Open AccessNo selection lemma for empty triangles
- Open Access
No Selection Lemma for Empty Triangles
Let $S$ be a set of $n$ points in general position in the plane. The Second Selection Lemma states that for any family of $\Theta(n^3)$ triangles spanned by $S$, there exists a point of the plane that lies in a constant fraction of them. For families of $\Theta(n^{3-\alpha})$ triangles, with $0\le \alpha \le 1$, there might not be a point in more than $\Theta(n^{3-2\alpha})$ of those triangles. An empty triangle of $S$ is a triangle spanned by $S$ not containing any point of $S$ in its interior. B\'ar\'any conjectured that there exist an edge spanned by $S$ that is incident to a super constant number of empty triangles of $S$. The number of empty triangles of $S$ might be $O(n^2)$; in such a case, on average, every edge spanned by $S$ is incident to a constant number of empty triangles. The conjecture of B\'ar\'any suggests that for the class of empty triangles the above upper bound might not hold. In this paper we show that, somewhat surprisingly, the above upper bound does in fact hold for empty triangles. Specifically, we show that for any integer $n$ and real number $0\leq \alpha \leq 1$ there exists a point set of size $n$ with $\Theta(n^{3-\alpha})$ empty triangles such that any point of the plane is only in $O(n^{3-2\alpha})$ empty triangles.Open AccessNo Selection Lemma for Empty Triangles
Let $S$ be a set of $n$ points in general position in the plane. The Second Selection Lemma states that for any family of $\Theta(n^3)$ triangles spanned by $S$, there exists a point of the plane that lies in a constant fraction of them. For families of $\Theta(n^{3-\alpha})$ triangles, with $0\le \alpha \le 1$, there might not be a point in more than $\Theta(n^{3-2\alpha})$ of those triangles. An empty triangle of $S$ is a triangle spanned by $S$ not containing any point of $S$ in its interior. B\'ar\'any conjectured that there exist an edge spanned by $S$ that is incident to a super constant number of empty triangles of $S$. The number of empty triangles of $S$ might be $O(n^2)$; in such a case, on average, every edge spanned by $S$ is incident to a constant number of empty triangles. The conjecture of B\'ar\'any suggests that for the class of empty triangles the above upper bound might not hold. In this paper we show that, somewhat surprisingly, the above upper bound does in fact hold for empty triangles. Specifically, we show that for any integer $n$ and real number $0\leq \alpha \leq 1$ there exists a point set of size $n$ with $\Theta(n^{3-\alpha})$ empty triangles such that any point of the plane is only in $O(n^{3-2\alpha})$ empty triangles. - 3 September 2021
- Published by Springer Nature in Acta Mathematica Hungarica
- Vol. 165 (1) , 28-39
Non-crossing monotone paths and binary trees in edge-ordered complete geometric graphs
- 3 September 2021
- Published by Springer Nature in Acta Mathematica Hungarica
- Vol. 165 (1) , 28-39
Non-crossing monotone paths and binary trees in edge-ordered complete geometric graphs
- Open Access
- 1 January 2021
- Published by Elsevier in Information Processing Letters
- Vol. 165, 106028
Counting the number of crossings in geometric graphs
- 1 January 2021
- Published by Elsevier in Information Processing Letters
- Vol. 165, 106028
Open AccessCounting the number of crossings in geometric graphs
- 19 November 2020
- Published by Elsevier in Computational Geometry
- Vol. 95, 101730
On the number of order types in integer grids of small size
- 19 November 2020
- Published by Elsevier in Computational Geometry
- Vol. 95, 101730
On the number of order types in integer grids of small size
- Open Access
Counting the Number of Crossings in Geometric Graphs
A geometric graph is a graph whose vertices are points in general position in the plane and its edges are straight line segments joining these points. In this paper we give an $O(n^2 \log n)$ algorithm to compute the number of pairs of edges that cross in a geometric graph on $n$ points. For layered, and convex geometric graphs the algorithm takes $O(n^2)$ time.Open AccessCounting the Number of Crossings in Geometric Graphs
A geometric graph is a graph whose vertices are points in general position in the plane and its edges are straight line segments joining these points. In this paper we give an $O(n^2 \log n)$ algorithm to compute the number of pairs of edges that cross in a geometric graph on $n$ points. For layered, and convex geometric graphs the algorithm takes $O(n^2)$ time. - Open Access
Chirotopes of Random Points in Space are Realizable on a Small Integer Grid
We prove that with high probability, a uniform sample of $n$ points in a convex domain in $\mathbb{R}^d$ can be rounded to points on a grid of step size proportional to $1/n^{d+1+\epsilon}$ without changing the underlying chirotope (oriented matroid). Therefore, chirotopes of random point sets can be encoded with $O(n\log n)$ bits. This is in stark contrast to the worst case, where the grid may be forced to have step size $1/2^{2^{\Omega(n)}}$ even for $d=2$. This result is a high-dimensional generalization of previous results on order types of random planar point sets due to Fabila-Monroy and Huemer (2017) and Devillers, Duchon, Glisse, and Goaoc (2018).Open AccessChirotopes of Random Points in Space are Realizable on a Small Integer Grid
We prove that with high probability, a uniform sample of $n$ points in a convex domain in $\mathbb{R}^d$ can be rounded to points on a grid of step size proportional to $1/n^{d+1+\epsilon}$ without changing the underlying chirotope (oriented matroid). Therefore, chirotopes of random point sets can be encoded with $O(n\log n)$ bits. This is in stark contrast to the worst case, where the grid may be forced to have step size $1/2^{2^{\Omega(n)}}$ even for $d=2$. This result is a high-dimensional generalization of previous results on order types of random planar point sets due to Fabila-Monroy and Huemer (2017) and Devillers, Duchon, Glisse, and Goaoc (2018). - 18 December 2018
- Published by Springer Nature
- p. 593-605
Optimal Grid Drawings of Complete Multipartite Graphs and an Integer Variant of the Algebraic Connectivity
- 18 December 2018
- Published by Springer Nature
- p. 593-605
Optimal Grid Drawings of Complete Multipartite Graphs and an Integer Variant of the Algebraic Connectivity
- Open Access
Optimal Grid Drawings of Complete Multipartite Graphs and an Integer Variant of the Algebraic Connectivity
How to draw the vertices of a complete multipartite graph $G$ on different points of a bounded $d$-dimensional integer grid, such that the sum of squared distances between vertices of $G$ is (i) minimized or (ii) maximized? For both problems we provide a characterization of the solutions. For the particular case $d=1$, our solution for (i) also settles the minimum-2-sum problem for complete bipartite graphs; the minimum-2-sum problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations are the solution for (ii). Such drawings are related with Laplacian eigenvalues of graphs. This motivates us to study which properties of the algebraic connectivity of graphs carry over to the restricted setting of drawings of graphs with integer coordinates.Open AccessOptimal Grid Drawings of Complete Multipartite Graphs and an Integer Variant of the Algebraic Connectivity
How to draw the vertices of a complete multipartite graph $G$ on different points of a bounded $d$-dimensional integer grid, such that the sum of squared distances between vertices of $G$ is (i) minimized or (ii) maximized? For both problems we provide a characterization of the solutions. For the particular case $d=1$, our solution for (i) also settles the minimum-2-sum problem for complete bipartite graphs; the minimum-2-sum problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations are the solution for (ii). Such drawings are related with Laplacian eigenvalues of graphs. This motivates us to study which properties of the algebraic connectivity of graphs carry over to the restricted setting of drawings of graphs with integer coordinates.