{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihoia3jcnfty633bk4qzm2s47xrli26rgqowcdm3e6mfy4cn7u7ei",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfb2umrxav32"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.16518v1",
  "publishedAt": "2026-02-19T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Mark de Berg",
    "Geert van Wordragen"
  ],
  "textContent": "**Authors:** Mark de Berg, Geert van Wordragen\n\nIn the planar one-round discrete Voronoi game, two players $\\mathcal{P}$ and $\\mathcal{Q}$ compete over a set $V$ of $n$ voters represented by points in $\\mathbb{R}^2$. First, $\\mathcal{P}$ places a set $P$ of $k$ points, then $\\mathcal{Q}$ places a set $Q$ of $\\ell$ points, and then each voter $v\\in V$ is won by the player who has placed a point closest to $v$. It is well known that if $k=\\ell=1$, then $\\mathcal{P}$ can always win $n/3$ voters and that this is worst-case optimal. We study the setting where $k>1$ and $\\ell=1$. We present lower bounds on the number of voters that $\\mathcal{P}$ can always win, which improve the existing bounds for all $k\\geq 4$. As a by-product, we obtain improved bounds on small $\\varepsilon$-nets for convex ranges. These results are for the $L_2$ metric. We also obtain lower bounds on the number of voters that $\\mathcal{P}$ can always win when distances are measured in the $L_1$ metric.",
  "title": "Improved Bounds for Discrete Voronoi Games"
}