{
  "id": "1612.04940",
  "version": "v1",
  "published": "2016-12-15T06:19:57.000Z",
  "updated": "2016-12-15T06:19:57.000Z",
  "title": "Distinct distances between a collinear set and an arbitrary set of points",
  "authors": [
    "Ariel Bruner",
    "Micha Sharir"
  ],
  "categories": [
    "math.CO",
    "math.MG"
  ],
  "abstract": "We consider the number of distinct distances between two finite sets of points in ${\\bf R}^k$, for any constant dimension $k\\ge 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 $$ \\Omega\\left(\\min\\left\\{ n^{2/3}m^{2/3},\\; \\frac{n^{10/11}m^{4/11}}{\\log^{2/11}m},\\; n^2,\\; m^2\\right\\}\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-12-15T06:19:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "distinct distances",
      "collinear set",
      "arbitrary set",
      "axis contains",
      "finite sets"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}