Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistinct distances between a collinear set and an arbitrary set of points
77
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider the number of distinct distances between two finite sets of points in ${bf R}^k$, for any constant dimension $kge 2$, where one set $P_1$ consists of $n$ points on a line $l$, and the other set $P_2$ consists of $m$ arbitrary points, such that no hyperplane orthogonal to $l$ and no hypercylinder having $l$ as its axis contains more than $O(1)$ points of $P_2$. The number of distinct distances between $P_1$ and $P_2$ is then $$ Omegaleft(minleft{ n^{2/3}m^{2/3},; frac{n^{10/11}m^{4/11}}{log^{2/11}m},; n^2,; m^2right}right) . $$ Without the assumption on $P_2$, there exist sets $P_1$, $P_2$ as above, with only $O(m+n)$ distinct distances between them.
rate research
Read More
We prove the following generalised empty pentagon theorem: for every integer $ell geq 2$, every sufficiently large set of points in the plane contains $ell$ collinear points or an empty pentagon. As an application, we settle the next open case of the big line or big clique conjecture of Kara, Por, and Wood [emph{Discrete Comput. Geom.} 34(3):497--506, 2005].
In this note we show that for each Latin square $L$ of order $ngeq 2$, there exists a Latin square $L eq L$ of order $n$ such that $L$ and $L$ differ in at most $8sqrt{n}$ cells. Equivalently, each Latin square of order $n$ contains a Latin trade of size at most $8sqrt{n}$. We also show that the size of the smallest defining set in a Latin square is $Omega(n^{3/2})$. %That is, there are constants $c$ and $n_0$ such that for any $n>n_0$ the size of the smallest defining %set of order $n$ is at least $cn^{3/2}$.
In this paper we investigate the extremal properties of the sum $$sum_{i=1}^n|MA_i|^{lambda},$$ where $A_i$ are vertices of a regular simplex, a cross-polytope (orthoplex) or a cube and $M$ varies on a sphere concentric to the sphere circumscribed around one of the given polytopes. We give full characterization for which points on $Gamma$ the extremal values of the sum are obtained in terms of $lambda$. In the case of the regular dodecahedron and icosahedron in $mathbb{R}^3$ we obtain results for which values of $lambda$ the corresponding sum is independent of the position of $M$ on $Gamma$. We use elementary analytic and purely geometric methods.
The emph{distance-number} of a graph $G$ is the minimum number of distinct edge-lengths over all straight-line drawings of $G$ in the plane. This definition generalises many well-known concepts in combinatorial geometry. We consider the distance-number of trees, graphs with no $K^-_4$-minor, complete bipartite graphs, complete graphs, and cartesian products. Our main results concern the distance-number of graphs with bounded degree. We prove that $n$-vertex graphs with bounded maximum degree and bounded treewidth have distance-number in $mathcal{O}(log n)$. To conclude such a logarithmic upper bound, both the degree and the treewidth need to be bounded. In particular, we construct graphs with treewidth 2 and polynomial distance-number. Similarly, we prove that there exist graphs with maximum degree 5 and arbitrarily large distance-number. Moreover, as $Delta$ increases the existential lower bound on the distance-number of $Delta$-regular graphs tends to $Omega(n^{0.864138})$.
We study ErdH oss distinct distances problem under $ell_p$ metrics with integer $p$. We improve the current best bound for this problem from $Omega(n^{4/5})$ to $Omega(n^{6/7-epsilon})$, for any $epsilon>0$. We also characterize the sets that span an asymptotically minimal number of distinct distances under the $ell_1$ and $ell_infty$ metrics.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
