\usetikzlibrary

intersections, plotmarks, arrows.meta, angles, quotes \tikzset dot/.style=circle,inner sep=1.7pt,fill,label=#1,name=#1, right angle quadrant/.code= \pgfmathsetmacro\quadranta1,1,-1,-1[#1-1] \pgfmathsetmacro\quadrantb1,-1,-1,1[#1-1], right angle quadrant=1, right angle length/.code=, right angle length=2ex, right angle symbol/.style n args=3 insert path= let \p0 = ( $(#1)!(#3)!(#2)$ ) in let \p1 = ( $(\p 0)!\quadranta*\rightanglelength!(#3)$ ), \p2 = ( $(\p 0)!\quadrantb*\rightanglelength!(#2)$ ) in let \p3 = ( $(\p 1)+(\p 2)-(\p 0)$ ) in (\p1) – (\p3) – (\p2) Tandon School of Engineering, New York University, Brooklyn, NY 11201, [email protected]://orcid.org/0000-0003-3110-4702Partially supported by NSF grant CCF-15-40656 and by grant 2014/170 from the US-Israel Binational Science Foundation. Department of Computing Science, TU Eindhoven, 5600 MB Eindhoven, The [email protected]://orcid.org/0000-0001-5770-3784Supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 024.002.003. School of Computer Science, University of Sydney, Sydney, NSW 2006, [email protected]://orcid.org/0000-0002-6778-7990Supported under the Australian Research Council Discovery Projects funding scheme (project numbers DP150101134 and DP180102870). Sportlogiq, Inc., Montreal, Quebec H2T 3B3, [email protected] https://orcid.org/0000-0001-6388-9634 \CopyrightBoris Aronov, Mark de Berg, Joachim Gudmundsson and Michael Horton \ccsdesc[100]Theory of computation Design and analysis of algorithms \EventEditorsSergio Cabello and Danny Z. Chen \EventNoEds2 \EventLongTitle36th International Symposium on Computational Geometry (SoCG 2020) \EventShortTitleSoCG 2020 \EventAcronymSoCG \EventYear2020 \EventDateJune 23–26, 2020 \EventLocationZürich, Switzerland \EventLogosocg-logo \SeriesVolume164 \ArticleNoXX \hideLIPIcs

On $\beta$ -Plurality Points in Spatial Voting Games

Boris Aronov Mark de Berg Joachim Gudmundsson Michael Horton

Abstract

Let $V$ be a set of $n$ points in ${\mathbb{R}}^{d}$ , called voters. A point $p\in{\mathbb{R}}^{d}$ is a plurality point for $V$ when the following holds: for every $q\in{\mathbb{R}}^{d}$ the number of voters closer to $p$ than to $q$ is at least the number of voters closer to $q$ than to $p$ . Thus, in a vote where each $v\in V$ votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal $p$ will not lose against any alternative proposal $q$ . For most voter sets a plurality point does not exist. We therefore introduce the concept of $\beta$ -plurality points, which are defined similarly to regular plurality points except that the distance of each voter to $p$ (but not to $q$ ) is scaled by a factor $\beta$ , for some constant $0<\beta\leqslant 1$ . We investigate the existence and computation of $\beta$ -plurality points, and obtain the following results.

•

Define $\beta^{*}_{d}\coloneqq\sup\{\beta:\text{any finite multiset $V$ in ${\mathbb{R}}^{d}$ admits a $\beta$-plurality point}\}$ . We prove that $\beta^{*}_{2}=\sqrt{3}/2$ , and that $1/\sqrt{d}\leqslant\beta^{*}_{d}\leqslant\sqrt{3}/2$ for all $d\geqslant 3$ .
•

Define $\beta(p,V)\coloneqq\sup\{\beta:\text{$p$ is a $\beta$-plurality point for $V$}\}$ . Given a voter set $V\in{\mathbb{R}}^{2}$ , we provide an algorithm that runs in $O(n\log n)$ time and computes a point $p$ such that $\beta(p,V)\geqslant\beta^{*}_{2}$ . Moreover, for $d\geqslant 2$ we can compute a point $p$ with $\beta(p,V)\geqslant 1/\sqrt{d}$ in $O(n)$ time.
•

Define $\beta(V)\coloneqq\sup\{\beta:\text{$V$ admits a $\beta$-plurality point}\}$ . We present an algorithm that, given a voter set $V$ in ${\mathbb{R}}^{d}$ , computes an $(1-\varepsilon)\cdot\beta(V)$ plurality point in time $O(\frac{n^{2}}{\varepsilon^{3d-2}}\cdot\log\frac{n}{\varepsilon^{d-1}}\cdot\log^{2}\frac{1}{\varepsilon})$ .

keywords:

Computational geometry, Spatial voting theory, Plurality point, Computational social choice

1 Introduction

Background.

Voting theory is concerned with mechanisms to combine preferences of individual voters into a collective decision. A desirable property of such a collective decision is that it is stable, in the sense that no alternative is preferred by more voters. In spatial voting games [5, 10] this is formalized as follows; see Fig. 1(i) for an example in a political context. The space of all possible decisions is modeled as ${\mathbb{R}}^{d}$ and every voter is represented by a point in ${\mathbb{R}}^{d}$ , where the dimensions represent different aspects of the decision and the point representing a voter corresponds to the ideal decision for that voter. A voter $v$ now prefers a proposed decision $p\in{\mathbb{R}}^{d}$ over some alternative proposal $q\in{\mathbb{R}}^{d}$ when $v$ is closer to $p$ than to $q$ . Thus a point $p\in{\mathbb{R}}^{d}$ represents a stable decision for a given finite set $V$ of voters if, for any alternative $q\in{\mathbb{R}}^{d}$ , we have $\left|\{v\in V:|vp|<|vq|\}\right|\geqslant\left|\{v\in V:|vq|<|vp|\}\right|$ . Such a point $p$ is called a plurality point.¹¹1One can also require $p$ to be strictly more popular than any alternative $q$ . This is sometimes called a strong plurality point, in contrast to the weak plurality points that we consider.

For $d=1$ , a plurality point always exists, since in ${\mathbb{R}}^{1}$ a median of $V$ is a plurality point. This is not true in higher dimensions, however. Define a median hyperplane for a set $V$ of voters to be a hyperplane $h$ such that both open half-spaces defined by $h$ contain fewer than $|V|/2$ voters. For $d\geqslant 2$ a plurality point in ${\mathbb{R}}^{d}$ exists if and only if all median hyperplanes for $V$ meet in a common point; see Fig. 1(ii). This condition is known as generalized Plott symmetry conditions [12, 24]; see also the papers by Wu et al. [29] and de Berg et al. [4], who present algorithms to determine the existence of a plurality point for a given set of voters.

It is very unlikely that voters are distributed in such a way that all median hyperplanes have a common intersection. (Indeed, if this happens, then a slightest generic perturbation of a single voter destroys the existence of the plurality point.) When a plurality point does not exist, we may want to find a point that is close to being a plurality point. One way to formalize this is to consider the center of the yolk (or plurality ball) of $V$ , where the yolk [14, 18, 22, 23] is the smallest ball intersecting every median hyperplane of $V$ . We introduce $\beta$ -plurality points as an alternative way to relax the requirements for a plurality point, and study several combinatorial and algorithmic questions regarding $\beta$ -plurality points.

Refer to caption — Fig. 1: (i) The US presidential candidates 2016 modelled in the spatial voting model, according to The Political Compass (https://politicalcompass.org/uselection2016). Note that the points representing voters are not shown. (ii) The point set satisfies the generalized Plott symmetry conditions and therefore admits a plurality point.

$\beta$ -Plurality points: definition and main questions.

Let $V$ be a multiset²²2Even though we allow $V$ to be a multiset, we sometimes refer to it as a “set” to ease the reading. When the fact that $V$ is a multiset requires special treatment, we explicitly address this. of $n$ voters in ${\mathbb{R}}^{d}$ in arbitrary, possibly coinciding, positions. In the traditional setting a proposed point $p\in{\mathbb{R}}^{d}$ wins a voter $v\in V$ against an alternative $q$ if $|pv|<|qv|$ . We relax this by fixing a parameter $\beta$ with $0<\beta\leqslant 1$ and letting $p$ win $v$ against $q$ if $\beta\cdot|pv|<|qv|$ . Thus we give an advantage to the initial proposal $p$ by scaling distances to $p$ by a factor $\beta\leqslant 1$ . We now define

V[p\succ_{\beta}q]\coloneqq\{v\in V:\beta\cdot|pv|<|qv|\}\quad\text{and}\quad V[p\prec_{\beta}q]\coloneqq\{v\in V:\beta\cdot|pv|>|qv|\}

to be the multisets of voters won by $p$ over $q$ and lost by $p$ against $q$ , respectively. Finally, we say that a point $p\in{\mathbb{R}}^{d}$ is a $\beta$ -plurality point for $V$ when

\left|V[p\succ_{\beta}q]\right|\geqslant\left|V[p\prec_{\beta}q]\right|,\quad\text{for any point $q\in{\mathbb{R}}^{d}$}.

Observe that $\beta$ -plurality is monotone in the sense that if $p$ is a $\beta$ -plurality point then $p$ is also a $\beta^{\prime}$ -plurality point for all $\beta^{\prime}<\beta$ .

The spatial voting model was popularised by Black [5] and Down [10] in the 1950s. Stokes [27] criticized its simplicity and was the first to highlight the importance of taking non-spatial aspects into consideration. The reasoning is that voters may evaluate a candidate not only on their policies—their position in the policy space—but also take their so-called valence into account: charisma, competence, or other desirable qualities in the public’s mind [13]. A candidate can also increase her valence by a stronger party support [28] or campaign spending [19]. Several models have been proposed to bring the spatial model closer to a more realistic voting approach; see [16, 17, 25] as examples. A common model is the multiplicative model, introduced by Hollard and Rossignol [20], which is closely related to the concept of a $\beta$ -plurality point. The multiplicative model augments the existing spatial utility function by scaling the candidate’s valence by a multiplicative factor. Note that in the 2-player game considered in this paper the multiplicative model is the same as our $\beta$ -plurality model. From a computational point of view very little is known about the multiplicative model. We are only aware of a result by Chung [8], who studied the problem of positioning a new candidate in an existing space of voters and candidates, so that the valence required to win at least a given number of voters is minimized.

One reason for introducing $\beta$ -plurality was that a set $V$ of voters in ${\mathbb{R}}^{d}$ , for $d\geqslant 2$ , generally does not admit a plurality point. This immediately raises the question: Is it true that, for $\beta$ small enough, any set $V$ admits a $\beta$ -plurality point? If so, we want to know the largest $\beta$ such that any voter set $V$ admits a $\beta$ -plurality point, that is, we wish to determine

\beta^{*}_{d}\coloneqq\sup\{\beta:\text{any finite multiset $V$ in ${\mathbb{R}}^{d}$ admits a $\beta$-plurality point}\}.

Note that $\beta^{*}_{1}=1$ , since any set $V$ in ${\mathbb{R}}^{1}$ admits a plurality point and 1-plurality is equivalent to the traditional notion of plurality.

After studying this combinatorial problem in Section 2, we turn our attention to the following algorithmic question: given a voter set $V$ , find a point $p$ that is a $\beta$ -plurality point for the largest possible value $\beta$ . In other words, if we define

\beta(V)\coloneqq\sup\{\beta:\mbox{$V$ admits a $\beta$-plurality point}\}

and

\beta(p,V)\coloneqq\sup\{\beta:\mbox{$p$ is a $\beta$-plurality point for $V$}\}

then we want to find a point $p$ such that $\beta(p,V)=\beta(V)$ .

Results.

In Section 2 we prove that $\beta^{*}_{d}\leqslant\sqrt{3}/2$ for all $d\geqslant 2$ . To this end we first show that $\beta^{*}_{d}$ is non-increasing in $d$ , and then we exhibit a voter set $V$ in ${\mathbb{R}}^{2}$ such that $\beta(V)\leqslant\sqrt{3}/2$ . We also show how to construct in $O(n\log n)$ time, for any given $V$ in ${\mathbb{R}}^{2}$ , a point $p$ such that $\beta(p,V)\geqslant\sqrt{3}/2$ , thus proving that $\beta^{*}_{2}=\sqrt{3}/2$ . Moreover, for $d\geqslant 2$ we show how to construct in $O(n)$ time a point $p$ such that $\beta(p,V)\geqslant 1/\sqrt{d}$ , which means that $\beta^{*}_{d}\geqslant 1/\sqrt{d}$ .³³3Very recently Filtser and Filtser [15] improved these results for $d\geqslant 4$ by proving that $\beta^{*}_{d}\geqslant\frac{1}{2}\sqrt{\frac{1}{2}+\sqrt{3}-\frac{1}{2}\sqrt{4\sqrt{3}-3}}\approx 0.557$ for any $d\geqslant 4$ .

In Section 3 we study the problem of computing, for a given voter set $V$ of $n$ points in ${\mathbb{R}}^{d}$ , a $\beta$ -plurality point for the largest possible $\beta$ . (Here we assume $d$ to be a fixed constant.) While such a point can be found in polynomial time, the resulting running time is quite high. We therefore focus our attention on finding an approximately optimal point $p$ , that is, a point $p$ such that $\beta(p,V)\geqslant(1-\varepsilon)\cdot\beta(V)$ . We show that such a point can be computed in $O(\frac{n^{2}}{\varepsilon^{3d-2}}\cdot\log\frac{n}{\varepsilon^{d-1}}\cdot\log^{2}\frac{1}{\varepsilon})$ time.

Notation.

We denote the open ball of radius $\rho$ centered at a point $q\in{\mathbb{R}}^{d}$ by $B(q,\rho)$ and, for a point $p\in{\mathbb{R}}^{d}$ and a voter $v$ , we define $D_{\beta}(p,v)\coloneqq B(v,\beta\cdot|pv|)$ . Observe that $p$ wins $v$ against a competitor $q$ if and only if $q$ is strictly outside $D_{\beta}(p,v)$ , while $q$ wins $v$ if and only if $q$ is strictly inside $D_{\beta}(p,v)$ . Hence, $V[p\prec_{\beta}q]=\{v\in V\colon q\in D_{\beta}(p,v)\}$ . We define $\mathcal{D}_{\beta}(p)\coloneqq\{D_{\beta}(p,v):v\in V\}$ —here we assume $V$ is clear from the context—and let $\mathcal{A}(\mathcal{D}_{\beta}(p))$ denote the arrangement induced by $\mathcal{D}_{\beta}(p)$ . The competitor point $q$ that wins the most voters against $p$ will thus lie in the cell of $\mathcal{A}(\mathcal{D}_{\beta}(p))$ of the greatest depth or, more precisely, the cell contained in the maximum number of disks $D_{\beta}(p,v)$ .

2 Bounds on $\beta^{*}_{d}$

In this section we will prove bounds on $\beta^{*}_{d}$ , the supremum of all $\beta$ such that any finite set $V\subset{\mathbb{R}}^{d}$ admits a $\beta$ -plurality point. We start with an observation that allows us to apply bounds on $\beta^{*}_{d}$ to those on $\beta^{*}_{d^{\prime}}$ for $d^{\prime}>d$ . Let $\mathrm{conv}(V)$ denote the convex hull of $V$ .

Observation \thetheorem.

Let $V$ be a finite multiset of voters in ${\mathbb{R}}^{d}$ .

(i)

Suppose a point $p\in{\mathbb{R}}^{d}$ is not a $\beta$ -plurality point for $V$ . Then there is a point $q\in\mathrm{conv}(V)$ such that $\left|V[p\succ_{\beta}q]\right|<\left|V[p\prec_{\beta}q]\right|$ .
(ii)

For any $p^{\prime}\not\in\mathrm{conv}(V)$ , there is a point $p\in\mathrm{conv}(V)$ with $\beta(p,V)>\beta(p^{\prime},V)$ .
(iii)

For any $d^{\prime}>d$ we have $\beta_{d^{\prime}}^{*}\leqslant\beta_{d}^{*}$ .

Proof.

Note that for every point $r\not\in\mathrm{conv}(V)$ there is a point $r^{\prime}\in\mathrm{conv}(V)$ that lies strictly closer to all voters in $V$ , namely the point $r^{\prime}\in\partial\mathrm{conv}(V)$ closest to $r^{\prime}$ . This immediately implies part (i): if $p$ is beaten by some point $q\not\in\mathrm{conv}(V)$ then $p$ is certainly beaten by a point $q^{\prime}\in\mathrm{conv}(V)$ that lies strictly closer to all voters in $V$ than $q$ . It also immediately implies part (ii), because if a point $p$ lies strictly closer to all voters in $V$ than a point $p^{\prime}$ , then $\beta(p,V)>\beta(p^{\prime},V)$ .

To prove part (iii), let $V\in{\mathbb{R}}^{d}$ be a voter set such that $\beta(V)=\beta^{*}_{d}$ . Now embed $V$ into ${\mathbb{R}}^{d^{\prime}}$ , say in the flat $x_{d+1}=\cdots=x_{d^{\prime}}=0$ , obtaining a set $V^{\prime}$ . Then $\beta(V^{\prime})=\beta(V)$ by parts (i) and (ii). Hence, $\beta_{d^{\prime}}^{*}\leqslant\beta(V^{\prime})=\beta(V)=\beta_{d}^{*}$ . ∎

We can now prove an upper bound on $\beta_{d}^{*}$ .

Lemma 2.1.

$\beta_{d}^{*}\leqslant\sqrt{3}/2$ , for $d\geqslant 2$ .

Proof 2.2.

By Observation 2(iii), it suffices to prove the lemma for $d=2$ . To this end let $V=\{v_{1},v_{2},v_{3}\}$ consist of three voters that form an equilateral triangle $\Delta$ of side length 2 in ${\mathbb{R}}^{2}$ ; see Fig. 2(i).

Let $p$ denote the center of $\Delta$ . We will first argue that $\beta(p,V)=\sqrt{3}/2$ . Note that $|pv_{i}|=2/\sqrt{3}$ for all three voters $v_{i}$ . Hence, for $\beta=\sqrt{3}/2$ , the open balls $D_{\beta}(v_{i},p)$ are pairwise disjoint and touching at the mid-points of the edges of $\Delta$ . Therefore any competitor $q$ either wins one voter and loses the remaining two, or wins no voter and loses at least one. The former happens when $q$ lies inside one of the three balls $D_{\beta}(v_{i},p)$ ; the later happens when $q$ does not lie inside any of the balls, because in that case $q$ can be on the boundary of at most two of the balls. Thus, for $\beta=\sqrt{3}/2$ , the point $p$ always wins more voters than $q$ does. On the other hand, for $\beta>\sqrt{3}/2$ , any two balls $D_{\beta}(v_{i},p)$ , $D_{\beta}(v_{j},p)$ intersect and so a point $q$ located in such a pairwise intersection wins two voters and beats $p$ . We conclude that $\beta(p,V)=\sqrt{3}/2$ , as claimed.

The lemma now follows if we can show that $\beta(p^{\prime},V)\leqslant\sqrt{3}/2$ for any $p^{\prime}\neq p$ . Let $\mathrm{Vor}(V)$ be the Voronoi diagram of $V$ , and let $\mathcal{V}(v_{i})$ be the closed Voronoi cell of $v_{i}$ , as shown in Fig. 2(ii). Assume without loss of generality that $p^{\prime}$ lies in $\mathcal{V}(v_{3})$ . Let $E$ be the ellipse with foci $v_{1}$ and $v_{2}$ that passes through $p$ . Thus

E\coloneqq\{z\in{\mathbb{R}}^{2}:|zv_{1}|+|zv_{2}|=4/\sqrt{3}\}.

Note that $E$ is tangent to $\mathcal{V}(v_{3})$ at the point $p$ . Hence, any point $p^{\prime}\neq p$ in $\mathcal{V}(v_{3})$ has $|p^{\prime}v_{1}|+|p^{\prime}v_{2}|>4/\sqrt{3}$ . This implies that for $\beta\geqslant\sqrt{3}/2$ we have $\beta\cdot|p^{\prime}v_{1}|+\beta\cdot|p^{\prime}v_{2}|>2$ , and so the disks $D_{\beta}(p^{\prime},v_{1})$ and $D_{\beta}(p^{\prime},v_{2})$ intersect. It follows that for $\beta\geqslant\sqrt{3}/2$ there is a competitor $q$ that wins two voters against $p^{\prime}$ , which implies $\beta(p^{\prime},V)\leqslant\sqrt{3}/2$ and thus finishes the proof of the lemma.

We now prove lower bounds on $\beta_{d}^{*}$ . We first prove that $\beta_{d}^{*}\geqslant 1/\sqrt{d}$ for any $d\geqslant 2$ , and then we improve the lower bound to $\sqrt{3}/2$ for $d=2$ . The latter bound is tight by Lemma 2.1.

Let $V$ be a finite multiset of $n$ voters in ${\mathbb{R}}^{d}$ . We call a hyperplane $h$ balanced with respect to $V$ , if both open half-spaces defined by $h$ contain at most $n/2$ voters from $V$ . Note the difference with median hyperplanes, which are required to have fewer than $n/2$ voters in both open half-spaces. Clearly, for any $1\leqslant i\leqslant d$ there is a balanced hyperplane orthogonal to the $x_{i}$ -axis, namely the hyperplane $x_{i}=m_{i}$ , where $m_{i}$ is a median in the multiset of all $x_{i}$ -coordinates of the voters in $V$ . (In fact, for any direction $\vec{d}$ there is a balanced hyperplane orthogonal to $\vec{d}$ .)

Lemma 2.3.

Let $d\geqslant 2$ . For any finite multi-set $V$ of voters in ${\mathbb{R}}^{d}$ there exists a point $p\in{\mathbb{R}}^{d}$ such that $\beta(p,V)=1/\sqrt{d}$ . Moreover, such a point $p$ can be computed in $O(n)$ time.

Proof 2.4.

Let $\mathcal{H}\coloneqq\{h_{1},\dotsc,h_{d}\}$ be a set of balanced hyperplanes with respect to $V$ such that $h_{i}$ is orthogonal to the $x_{i}$ -axis, and assume without loss of generality that $h_{i}$ is the hyperplane $x_{i}=0$ . We will prove that the point $p$ located at the origin is a $\beta$ -plurality point for $V$ for any $\beta<1/\sqrt{d}$ , thus showing that $\beta(p,V)\geqslant 1/\sqrt{d}$ .

Let $q=(q_{1},\ldots,q_{d})$ be any competitor of $p$ . We can assume without loss of generality that $\max_{1\leqslant i\leqslant d}|q_{i}|=q_{d}>0$ . Thus $q$ lies in the closed cone $C_{d}^{+}$ defined as

C_{d}^{+}\coloneqq\{\ (x_{1},\ldots,x_{d})\in{\mathbb{R}}^{d}:\ x_{d}\geqslant|x_{j}|\mbox{ for all $j\neq d$ }\}.

Note that $C_{d}^{+}$ is bounded by portions of the $2(d-1)$ hyperplanes $x_{d}=\pm x_{j}$ with $j\neq d$ ; see Fig. 3.

Because $h_{d}\colon x_{d}=0$ is a balanced hyperplane, the open halfspace $h^{+}_{d}\colon x_{d}>0$ contains at most $n/2$ voters, which implies that the closed halfspace $\mathrm{cl}(h_{d}^{-})\colon x_{d}\leqslant 0$ contains at least $n/2$ voters. Hence, it suffices to argue that for any $\beta<1/\sqrt{d}$ the point $p$ wins all the voters in $\mathrm{cl}(h_{d}^{-})$ against $q$ .

Claim. For any voter $v\in\mathrm{cl}(h_{d}^{-})$ with $v\neq p$ , we have that $\sin\left(\angle qpv\right)\geqslant 1/\sqrt{d}$ with equality if and only if $q$ lies on an edge of $C_{d}^{+}$ and $v$ lies on the orthogonal projection of this edge onto $h_{d}$ .

Proof. For any point $v$ below $h_{d}$ there is a point $v^{\prime}\in h_{d}$ with $\angle qpv^{\prime}<\angle qpv$ , namely the orthogonal projection of $v$ onto $h_{d}$ . Hence, from now on we assume that $v\in h_{d}$ .

First, we prove that $\sin(\angle qpv)=1/\sqrt{d}$ if $q$ lies on an edge $e$ of $C_{d}^{+}$ and $v$ lies on the orthogonal projection $\overline{e}$ of $e$ onto $h_{d}$ . Assume without loss of generality that $e$ is the edge of $C_{d}^{+}$ defined by the intersection of the $d-1$ hyperplanes $x_{d}=x_{j}$ , so that $q_{1}=\dots=q_{d-1}=q_{d}$ . Since $\angle qpv$ is the same for any $v\in\overline{e}$ , we may assume that $v$ is the orthogonal projection of $q$ to $h_{d}$ , which means $|qv|=q_{d}$ . We then have

$\sin\left(\angle{qpv}\right)=\frac{|qv|}{|pq|}=\frac{q_{d}}{\sqrt{q_{1}^{2}+\dots+q_{d}^{2}}}=\frac{1}{\sqrt{d}}\,.$

Now assume the condition for equality does not hold. Let $\rho$ be the ray starting at $p$ and containing $q$ , and let $\overline{\rho}$ be its orthogonal projection onto $h_{d}$ . We have two cases: $v\in\overline{\rho}$ but $q$ is not contained in an edge of $C_{d}^{+}$ , or $v\not\in\overline{\rho}$ .

In the former case we may, as before, assume that $v$ is the projection of $q$ onto $h_{d}$ . Since $q\in C_{d}^{+}$ we have $q_{d}\geqslant|q_{j}|$ for all $j$ . Moreover, since $q$ does not lie on an edge of $C_{d}^{+}$ we have $q_{d}>|q_{j*}|$ for at least one $j^{*}$ . Thus $|pq|=\sqrt{q_{1}^{2}+\dotsc+q_{d}^{2}}<\sqrt{d\cdot q_{d}^{2}}=\sqrt{d}\cdot|qv|$ , and $\sin\left(\angle{qpv}\right)=|qv|/|pq|>1/\sqrt{d}$ .

In the latter case, let $\ell$ be the line containing $p$ and $v$ , and let $v^{\prime}$ be the point on $\ell$ closest to $q$ . Then $|qv|\geqslant|qv^{\prime}|>|q\overline{q}|$ , where $\overline{q}$ is the projection of $q$ onto $h_{d}$ , and so

$\sin\left(\angle{qpv}\right)\geqslant\frac{|qv^{\prime}|}{|pq|}>\frac{|q\overline{q}|}{|pq|}\geqslant\frac{1}{\sqrt{d}}\,.$

We can now use the Law of Sines and the claim above to derive that for any $\beta<1/\sqrt{d}$ and any voter $v\in\mathrm{cl}(h_{d}^{-})$ with $v\neq p$ we have

\beta\cdot|pv|<\frac{1}{\sqrt{d}}\cdot|pv|=\frac{1}{\sqrt{d}}\cdot\frac{|qv|\cdot\sin\left(\angle pqv\right)}{\sin\left(\angle qpv\right)}\leqslant|qv|\cdot\sin\left(\angle pqv\right)\leqslant|qv|\,.

Hence, $p$ wins every point in $\mathrm{cl}(h_{d}^{-})$ . This proves the first part of the lemma since $\mathrm{cl}(h_{d}^{-})$ contains at least $n/2$ voters, as already remarked.

Computing the point $p$ is trivial once we have the balanced hyperplanes $h_{i}$ , which can be found in $O(n)$ time by computing a median $x_{i}$ -coordinate for each $1\leqslant i\leqslant d$ .

A tight bound in the plane. In ${\mathbb{R}}^{2}$ we can improve the above bound: for any voter set $V$ in the plane we can find a point $p$ with $\beta(p,V)\geqslant\sqrt{3}/2$ . By Lemma 2.1, this bound is tight. The improvement is based on the following lemma.

Lemma 2.5.

Let $V$ be a multiset of $n$ voters in ${\mathbb{R}}^{2}$ , let $\ell_{1},\ell_{2},\ell_{3}$ be a triple of concurrent balanced lines such that the smaller angle between any two of them is $\frac{\pi}{3}$ , and let $p$ be the common intersection of $\ell_{1},\ell_{2},\ell_{3}$ . Then $\beta(p,V)\geqslant\sqrt{3}/2$ .

Proof 2.6.

Let $q$ be a competitor of $p$ . The three lines $\ell_{1},\ell_{2},\ell_{3}$ partition the plane into six equal-sized sectors, which we number $S_{1}$ through $S_{6}$ in a clockwise fashion, so that $q$ lies in the closure of $S_{1}$ ; see Figure 4. Let $H$ be the closure of $S_{3}\cup S_{4}\cup S_{5}$ . It is a closed halfspace bounded by a balanced line, so it contains at least half the voters.

Using an analysis similar to that in the proof of Lemma 2.3, we can show that $p$ does not lose any voter $v\in H$ . Indeed, using the Law of Sines we obtain

\frac{\sqrt{3}}{2}\cdot|pv|=\frac{\sqrt{3}}{2}\cdot\frac{\sin{\angle{pqv}}}{\sin{\angle{qpv}}}\cdot|qv|\leqslant|qv|,\quad\text{since}\quad\angle{qpv}\geqslant\pi/3,

which shows that $p$ is a $\beta$ -plurality point for any $\beta<\sqrt{3}/2$ . Hence, $\beta(p,V)\geqslant\sqrt{3}/2$ .

The main question is whether a triple of concurrent lines as in Lemma 2.5 always exists. The next lemma shows that this is indeed the case. The lemma—in fact a stronger version, stating that any two opposite cones defined by the three concurrent lines contain the same number of points—has been proved for even $n$ by Dumitrescu et al. [11]. Our proof of Lemma 2.7 is similar to their proof. We give it because we also need it for odd $n$ , and because we will need an understanding of the proof to describe our algorithm for computing the concurrent triple in the lemma. Our algorithm will run in $O(n\log n)$ time, a significant improvement over the $O(n^{4/3}\log^{1+\varepsilon}n)$ running time obtained (for the case of even $n$ ) by Dumitrescu et al. [11].

Lemma 2.7.

For any multiset $V$ of $n$ voters in ${\mathbb{R}}^{2}$ , there exists a triple of concurrent balanced lines $(\ell_{1},\ell_{2},\ell_{3})$ such that the smaller angle between any two of them is $\frac{\pi}{3}$ .

Proof 2.8.

Define the orientation of a line to be the counterclockwise angle it makes with the positive $y$ -axis. Recall that for any given orientation $\theta$ there exists at least one balanced line with orientation $\theta$ . When $n$ is odd this line is unique: it passes through the median of the voter set $V$ when $V$ is projected orthogonally onto a line orthogonal to the lines of orientation $\theta$ .

In the rest of the proof it will be convenient to have a unique balanced line for any orientation $\theta$ . To achieve this when $n$ is even, we simply delete an arbitrary voter from $V$ . (If there are other voters at the same location, these voters are not deleted.) This is allowed because when $|V|$ is even, a balanced line for $V\setminus\{v\}$ is also a balanced line for $V$ .

Now let $\mu$ be the function that maps an angle value $\theta$ to the unique balanced line $\mu(\theta)$ ; see Figure 5(i). Note that $\mu$ is continuous for $0\leqslant\theta<\pi$ . Let $\ell_{1}(\theta)\coloneqq\mu(\theta)$ , and $\ell_{2}(\theta)\coloneqq\mu(\theta+\frac{\pi}{3})$ , and $\ell_{3}(\theta)\coloneqq\mu(\theta+\frac{2\pi}{3})$ . For $i\neq j$ , let $p_{ij}(\theta)\coloneqq\ell_{i}(\theta)\cap\ell_{j}(\theta)$ be the intersection point between $\ell_{i}(\theta)$ and $\ell_{j}(\theta)$ . If $p_{23}(0)\in\ell_{1}(0)$ then the lines $\ell_{1}(0),\ell_{2}(0),\ell_{3}(0)$ are concurrent and we are done. Otherwise, consider the situation at $\theta=0$ and imagine $\ell_{1}(0)$ and $\ell_{2}(0)$ to be directed in the positive $y$ -direction, as in Fig. 5(ii). Clearly, if $p_{23}(0)$ is to the left of the directed line $\ell_{1}(0)$ then $p_{13}(0)$ is to the right of the directed line $\ell_{2}(0)$ , and vice versa. Now increase $\theta$ from $0$ to $\pi/3$ , and note that $\ell_{1}(\pi/3)=\ell_{2}(0)$ and $p_{23}(\pi/3)=p_{13}(0)$ . Hence, $p_{23}(\theta)$ lies to a different side of the directed line $\ell_{1}(\theta)$ for $\theta=0$ than it does for $\theta=\pi/3$ . Since both $\ell_{1}(\theta)$ and $p_{23}(\theta)$ vary continuously with $\theta$ , this implies that, for some $\bar{\theta}\in(0,\pi/3)$ , the point $p_{23}(\bar{\theta})$ crosses the line $\ell_{1}(\bar{\theta})$ , and so the lines $\ell_{1}(\bar{\theta}),\ell_{2}(\bar{\theta}),\ell_{3}(\bar{\theta})$ are concurrent.

The previous two lemmas show that any voter set $V$ in ${\mathbb{R}}^{2}$ admits a point $p$ such that $\beta(p,V)\geqslant\sqrt{3}/2$ . We now show that we can compute such a point in $O(n\log n)$ time, namely, we show how to compute a triple as in Lemma 2.7 in $O(n\log n)$ time. We follow the definitions and notation from the proof of that lemma. We will assume that $n$ is odd, which, as argued, is without loss of generality.

To find a concurrent triple of balanced lines, we first compute the lines $\ell_{1}(0),\ell_{2}(0),\ell_{3}(0)$ in $O(n)$ time. If they are concurrent, we are done. Otherwise, there is a $\bar{\theta}\in(0,\pi/3)$ such that $\ell_{1}(\bar{\theta}),\ell_{2}(\bar{\theta}),\ell_{3}(\bar{\theta})$ are concurrent. To find this value $\bar{\theta}$ we dualize the voter set $V$ , using the standard duality transform that maps a point $(a,b)$ to the non-vertical line $y=ax+b$ and vice versa. Let $v^{*}$ denote the dual line of the voter $v$ , and let $V^{*}\coloneqq\{v^{*}:v\in V\}$ . Note that for $\theta\in(0,\pi/3)$ the lines $\ell_{1}(\theta),\ell_{2}(\theta),\ell_{3}(\theta)$ are all non-vertical, therefore their duals $\ell^{*}_{i}(\theta)$ are well-defined.

Consider the arrangement $\mathcal{A}(V^{*})$ defined by the duals of the voters. For $\theta\neq 0$ , define $\mathrm{slope}(\theta)$ to be the slope of the lines with orientation $\theta$ . Then $\mu^{*}(\theta)$ , the dual of $\mu(\theta)$ , is the intersection point of the vertical line $x=\mathrm{slope}(\theta)$ with $L_{\mathrm{med}}$ , the median level in $\mathcal{A}(V^{*})$ . (The median level of $\mathcal{A}(V^{*})$ is the set of points $q$ such that there are fewer than $n/2$ lines below $q$ and fewer than $n/2$ lines above $q$ ; this is well defined since we assume $n$ is odd. The median level forms an $x$ -monotone polygonal curve along edges of $\mathcal{A}(V^{*})$ .) Observe that the duals $\ell_{1}^{*}(\theta),\ell_{2}^{*}(\theta),\ell_{3}^{*}(\theta)$ all lie on $L_{\mathrm{med}}$ . For $\theta\in(0,\pi/3)$ , the $x$ -coordinate of $\ell_{1}^{*}(\theta)$ lies in $(-\infty,-1/\sqrt{3})$ , the $x$ -coordinate of $\ell_{2}^{*}(\theta)$ lies in $(-1/\sqrt{3},1/\sqrt{3})$ , and the $x$ -coordinate of $\ell_{3}^{*}(\theta)$ lies in $(1/\sqrt{3},\infty)$ .

We split $L_{\mathrm{med}}$ into three pieces corresponding to these ranges of the $x$ -coordinate. Let $E_{1}$ , $E_{2}$ , and $E_{3}$ denote the sets of edges forming the parts of $L_{\mathrm{med}}$ in the first, second, and third range, respectively, where edges crossing the vertical lines $x=-1/\sqrt{3}$ and $x=1/\sqrt{3}$ are split; see Fig. 6. Thus, for any $\theta\in(0,\pi/3)$ and for $i\in\{1,2,3\}$ , the point $\ell^{*}_{i}(\theta)$ lies on an edge in $E_{i}$ .

Recall that we want to find a value $\bar{\theta}\in(0,\pi/3)$ such that $\ell_{1}(\bar{\theta}),\ell_{2}(\bar{\theta}),\ell_{3}(\bar{\theta})$ are concurrent. For $-\infty<x<1/\sqrt{3}$ , let $\theta_{x}$ be such that $\mathrm{slope}(\theta_{x})=x$ , and for $i\in\{1,2,3\}$ define $p_{i}(x):=\ell^{*}_{i}(\theta_{x})$ . We are thus looking for a value $\bar{x}\in(-\infty,1/\sqrt{3})$ such that the three points $p_{1}(\bar{x}),p_{2}(\bar{x}),p_{3}(\bar{x})$ are collinear.

One way to find $\bar{x}$ would be to first explicitly compute $L_{\mathrm{med}}$ ; then we can increase $x$ , starting at $x=-\infty$ , and see how the points $p_{i}(x)$ move over $E_{i}$ , until we reach a value $\bar{x}$ such that $p_{1}(\bar{x}),p_{2}(\bar{x}),p_{3}(\bar{x})$ are collinear. Since the best known bounds on the complexity of the median level is $O(n^{4/3})$ [9] we will proceed differently, as follows.

1.

Use the recursive algorithm described below to find an interval $\bar{I}\subseteq\left(-\infty,1/\sqrt{3}\right)$ containing a value $\bar{x}$ with the desired property—namely, that the points $p_{1}(\bar{x})$ , $p_{2}(\bar{x})$ , and $p_{3}(\bar{x})$ are collinear—and such that, for any $i\in\{1,2,3\}$ , the point $p_{i}(x)$ lies on the same edge of $E_{i}$ for all $x\in\bar{I}$ .
2.

Find a value $\bar{x}\in\bar{I}$ such that $p_{1}(\bar{x})$ , $p_{2}(\bar{x})$ , and $p_{3}(\bar{x})$ are collinear. Since for $i=1,2,3$ each $p_{i}(x)$ lies on a fixed edge $e_{i}$ of $L_{\mathrm{med}}$ for all $x\in\bar{I}$ after Step 1, this can be done in $O(1)$ time. Indeed, if we go back to primal space we are given three (not necessarily distinct) voters $v_{1},v_{2},v_{3}$ (namely, the primals of the lines containing $e_{1}$ , $e_{2}$ , and $e_{3}$ ) and a range $(\theta,\theta^{\prime})$ of angles (corresponding to the $x$ -range $\bar{I}$ ), such that the line $\ell_{i}(\theta)$ passes through $v_{i}$ for any $\theta\in(\theta,\theta^{\prime})$ . We then only have to compute an orientation $\bar{\theta}\in(\theta,\theta^{\prime})$ such that the lines $\ell_{i}(\theta)$ meet in a common point—such an orientation $\bar{\theta}$ is guaranteed to exist by our construction of $\bar{I}$ .

We now explain the recursive algorithm used in Step 1. In a generic call we are given three trapezoids $\Delta_{1},\Delta_{2},\Delta_{3}$ that are each bounded by two non-vertical edges and two vertical edges (one of which may degenerate into a point). Let $I_{i}$ be the $x$ -range of $\Delta_{i}$ , for $i\in\{1,2,3\}$ ; note that this is well-defined since $\Delta_{i}$ is a trapezoid delimited by two vertical edges. The trapezoids $\Delta_{1},\Delta_{2},\Delta_{3}$ will have the following properties.

(P1)

Trapezoid $\Delta_{1}$ lies inside the vertical slab $(-\infty,-1/\sqrt{3})\times(-\infty,\infty)$ , trapezoid $\Delta_{2}$ lies inside the vertical slab $(-1/\sqrt{3},1/\sqrt{3})\times(-\infty,\infty)$ , and trapezoid $\Delta_{3}$ lies inside the vertical slab $(1/\sqrt{3},\infty)\times(-\infty,\infty)$ . Moreover, the $x$ -ranges $I_{1},I_{2},I_{3}$ correspond to each other in the following sense. Recall that an $x$ -range $I\subset(-\infty,-1/\sqrt{3})$ in the dual plane corresponds to an angular interval $(\phi,\phi^{\prime})$ in the primal plane. We denote by $I\oplus\theta$ the $x$ -range corresponding to the angular interval $(\phi+\theta,\phi^{\prime}+\theta)$ . The $x$ -ranges $I_{1},I_{2},I_{3}$ will be such that $I_{2}=I_{1}\oplus\frac{\pi}{3}$ and $I_{3}=I_{1}\oplus\frac{2\pi}{3}$ .
(P2)

For any $i\in\{1,2,3\}$ , the part of the median level $L_{\mathrm{med}}$ inside the vertical slab $I_{i}\times(-\infty,\infty)$ lies entirely inside $\Delta_{i}$ . Together with the property (P1) this implies that for any $x\in I_{1}$ we have that $p_{i}(x)\in\Delta_{i}$ , for $i\in\{1,2,3\}$ .
(P3)

Let $x_{\mathrm{left}}$ and $x_{\mathrm{right}}$ be such that $I_{1}=(x_{\mathrm{left}},x_{\mathrm{right}})$ . Then we have: If $p_{1}(x_{\mathrm{left}})$ lies above the line through $p_{2}(x_{\mathrm{left}})$ and $p_{3}(x_{\mathrm{left}})$ , then $p_{1}(x_{\mathrm{right}})$ lies below the line through $p_{2}(x_{\mathrm{right}})$ and $p_{3}(x_{\mathrm{right}})$ , and vice versa. This guarantees that there exists a value $\bar{x}\in I_{1}$ with the desired property and, hence, that $I_{1}$ contains the interval $\bar{I}$ we are looking for.

In a recursive call we are also given for each $\Delta_{i}$ the sets $V^{*}_{i}\subseteq V^{*}$ of lines intersecting the interior of $\Delta_{i}$ , as well as $n_{i}^{-}$ , the number of lines from $V^{*}$ passing completely below $\Delta_{i}$ .

Initially, $\Delta_{1}$ is the unbounded trapezoid⁴⁴4Since $x_{\mathrm{left}}=-\infty$ for this initial trapezoid $\Delta_{1}$ , the points $p_{i}(x_{\mathrm{left}})$ are not well defined. Recall, however, that in the primal plane the point on $L_{\mathrm{med}}$ “at $x=-\infty$ ” corresponds to the vertical balanced line $\ell_{1}(0)$ . Hence, we can derive the relative position of $p_{1}(-\infty)$ with respect to the line through $p_{2}(-\infty)$ and $p_{3}(-\infty)$ , from the relative position of the intersection point $\ell_{2}(0)\cap\ell_{3}(0)$ with respect to $\ell_{1}(0)$ . $(-\infty,-1/\sqrt{3})\times(-\infty,\infty)$ . Similarly, we initially have $\Delta_{2}=(-1/\sqrt{3},1/\sqrt{3})\times(-\infty,\infty)$ and $\Delta_{3}=(1/\sqrt{3},\infty)\times(-\infty,\infty)$ . Furthermore, $V^{*}_{i}=V^{*}$ and $n_{i}^{-}=0$ for $i=1,2,3$ .

The recursion ends when the interior of each $\Delta_{i}$ is intersected by a single edge of $L_{\mathrm{med}}$ ; we then have $\bar{I}:=I_{1}$ . The recursive call for a given triple $\Delta_{1},\Delta_{2},\Delta_{3}$ starts by shrinking $\Delta_{1}$ to a trapezoid $\Delta^{\prime}_{1}$ —thus zooming in on the value $\bar{x}$ —as follows. (We assume $|V^{*}_{1}|>1$ , otherwise the shrinking of $\Delta_{1}$ can be skipped.).

(i)

Set $r:=2$ and construct a $(1/r)$ -cutting for the lines in $V^{*}_{1}$ , clipped to within $\Delta_{1}$ . In other words, construct a partition $\Xi$ of $\Delta_{1}$ into $O(r^{2})=O(1)$ smaller trapezoids—see Fig. 7—such that the interior of each trapezoid $\tau\in\Xi$ is intersected by at most $n_{1}/2$ lines from $V^{*}_{1}$ , where $n_{1}:=|V^{*}_{1}|$ . Computing $\Xi$ can be done in $O(n_{1})$ time [6].
(ii)
Compute the intersections of $L_{\mathrm{med}}$ with the edges of each trapezoid $\tau\in\Xi$ in $O(n_{1}\log n_{1})$ time, as follows.
- •
  
  Consider a non-vertical edge $e$ of $\tau$ . First, compute the level of $p_{\mathrm{left}}$ , the left endpoint of $e$ . This can be done by counting the number of lines from $V^{*}_{1}$ below $p_{\mathrm{left}}$ and adding $n_{1}^{-}$ to this number. Next, intersect $e$ with all lines of $V^{*}_{1}$ and sort the intersections along $e$ , distinguishing lines that cross $e$ “from above” and “from below.” Finally, walk along $e$ , starting from $p_{\mathrm{left}}$ towards the right, increasing and decreasing the level according to the type of the intersection we encounter. All intersection points that lie on $L_{\mathrm{med}}$ can thus be reported. (For simplicity we ignore the case where $e$ partially or fully overlaps $L_{\mathrm{med}}$ . This can either be handled by a simple modification of the procedure, or we can avoid the situation altogether by modifying the cutting such that no edge $e$ of the cutting is contained in an input line.)
- •
  
  For a vertical edge $e$ of $\tau$ , we proceed similarly: first compute the level of the lower endpoint of $e$ , and then walk upward along $e$ until we reach an intersection point at the median level, or the upper endpoint of $e$ .
(iii)

The previous step gives us all intersection points of $L_{\mathrm{med}}$ with the edges of trapezoids in $\Xi$ . Let $X=\{\xi_{1},\ldots\xi_{|X|}\}$ be the sorted set of all $x$ -coordinates of these intersection points, as illustrated in Fig. 7. Note that $|X|=O(n_{1})$ . We perform a binary search on $X$ to find two consecutive $x$ -coordinates, $\xi_{i}$ and $\xi_{i+1}$ , such that the interval $(\xi_{i},\xi_{i+1})$ contains a value $\bar{x}$ with the desired property. Each step in the binary search can be done in $O(n_{1}+n_{2}+n_{3})$ time, as follows.

Assume without loss of generality that $p_{1}(x_{\mathrm{left}})$ lies above the line through $p_{2}(x_{\mathrm{left}})$ and $p_{3}(x_{\mathrm{left}})$ , and that $p_{1}(x_{\mathrm{right}})$ lies below the line through $p_{2}(x_{\mathrm{right}})$ and $p_{3}(x_{\mathrm{right}})$ . Suppose that during the binary search we arrive at some $\xi_{j}\in X$ , and we want to decide if we want to proceed to the left or to the right of $\xi_{j}$ . To do so, we first compute the points $p_{1}(\xi_{j})$ , $p_{2}(\xi_{j})$ , and $p_{3}(\xi_{j})$ . Point $p_{1}(\xi_{j})$ can be computed in $O(n_{1})$ time, as follows: first compute all intersections of the vertical line $x=\xi_{j}$ with the lines in $V^{*}_{1}$ , and then find the intersection point whose $y$ -coordinate has the appropriate rank, taking into account that there are $n_{1}^{-}$ lines from $V^{*}\setminus V^{*}_{1}$ fully below $\Delta_{1}$ . The points $p_{2}(\xi_{j})$ and $p_{3}(\xi_{j})$ can be computed in the same way—this takes $O(n_{2})$ and $O(n_{3})$ time, respectively—after determining their $x$ -coordinates in $O(1)$ time. (These $x$ -coordinate are $\mathrm{slope}(\theta_{\xi_{j}}+\pi/3)$ and $\mathrm{slope}(\theta_{\xi_{j}}+2\pi/3)$ , respectively.) After computing $p_{1}(\xi_{j})$ , $p_{2}(\xi_{j})$ , and $p_{3}(\xi_{j})$ we can make our decision: we proceed to the left if $p_{1}(\xi_{j})$ lies below the line through $p_{2}(\xi_{j})$ and $p_{3}(\xi_{j})$ , and to the right if $p_{1}(\xi_{j})$ lies above that line. (In the fortunate situation that $p_{1}(\xi_{j}),p_{2}(\xi_{j}),p_{3}(\xi_{j})$ are collinear, we can take $\bar{x}\coloneqq\xi_{j}$ and we are done.)

Since each step in the binary search takes $O(n_{1}+n_{2}+n_{3})$ time, the total binary search takes $O((n_{1}+n_{2}+n+3)\log n_{1})$ time. Sorting the set $X$ before the binary search only increases this by a constant factor.
(iv)

Finally, we take the two $x$ -coordinates $\xi_{i},\xi_{i+1}$ computed in the previous step, and find the points where $L_{\mathrm{med}}$ crosses the vertical lines $x=\xi_{i}$ and $x=\xi_{i+1}$ . Between $x=\xi_{i}$ and $x=\xi_{i+1}$ we know that $L_{\mathrm{med}}$ lies inside a single trapezoid $\tau\in\Xi$ . We then intersect $\tau$ with the slab $(\xi_{i},\xi_{i+1})\times(-\infty,\infty)$ , to obtain the trapezoid $\Delta^{\prime}_{1}$ . (If, for example, we would have $(\xi_{i},\xi_{i+1})=(\xi_{3},\xi_{4})$ in Fig. 7, then $\Delta^{\prime}_{1}$ is the grey trapezoid.) Note that the number of lines crossing $\Delta^{\prime}_{1}$ is at most $n_{1}/2$ and that the $x$ -range $I^{\prime}_{1}$ of $\Delta^{\prime}_{1}$ satisfies property (P3).

After shrinking $\Delta_{1}$ in this manner, we proceed as follows. We first clip $\Delta_{2}$ such that its $x$ -range corresponds to $I_{1}\oplus\frac{\pi}{3}$ , and then we shrink the clipped trapezoid $\Delta_{2}$ to a new trapezoid $\Delta^{\prime}_{2}$ in the same way as we shrunk $\Delta_{1}$ to $\Delta^{\prime}_{1}$ . Thus $\Delta^{\prime}_{2}$ is crossed by at most $n_{2}/2$ lines and $I^{\prime}_{2}\oplus\frac{-\pi}{3}$ satisfies property (P3), where $I^{\prime}_{2}$ is the $x$ -range of $\Delta^{\prime}_{2}$ . Next, we clip the $x$ -range of $\Delta_{3}$ to $I^{\prime}_{2}\oplus\frac{\pi}{3}$ , and then we apply the shrinking procedure to $\Delta_{3}$ to obtain a new trapezoid $\Delta^{\prime}_{3}$ . Finally, we clip $\Delta^{\prime}_{1}$ and $\Delta^{\prime}_{2}$ so that their $x$ -ranges correspond to $I^{\prime}_{3}\oplus\frac{-2\pi}{3}$ and $I^{\prime}_{3}\oplus\frac{-\pi}{3}$ , respectively. We then recurse on the triple $\Delta^{\prime}_{1},\Delta^{\prime}_{2},\Delta^{\prime}_{3}$ , passing along the appropriate sets $V^{*}_{i}$ and updating the counts $n_{i}^{-}$ .

The total time spent in all three shrinking steps is $O((n_{1}+n_{2}+n_{3})\log(n_{1}+n_{2}+n_{3}))$ , and each $n_{i}$ halves at every level in the recursion. Hence, the total time for Step 1 on page 1 is $O(n\log n)$ . As already mentioned, Step 2 takes only constant time. We can conclude that we can find a collinear triple $p_{1}(\bar{x}),p_{2}(\bar{x}),p_{3}(\bar{x})$ in $O(n\log n)$ time. In the primal this corresponds to a triple of collinear concurrent lines as in Lemma 2.5, so we obtain following theorem.

Theorem 2.9.

(i)

We have $\beta_{2}^{*}=\sqrt{3}/2$ . Moreover, for any multiset $V$ of $n$ voters in ${\mathbb{R}}^{2}$ we can compute a point $p$ with $\beta(p,V)\geqslant\sqrt{3}/2$ in $O(n\log n)$ time.
(ii)

For $d\geqslant 3$ , we have $1/\sqrt{d}\leqslant\beta_{d}^{*}\leqslant\sqrt{3}/2$ . Moreover, for any multiset $V$ of $n$ voters in ${\mathbb{R}}^{d}$ with $d\geqslant 2$ , we can compute a point $p$ with $\beta(p,V)\geqslant 1/\sqrt{d}$ in $O(n)$ time.

3 Finding a point that maximizes $\beta(p,V)$

We know from Theorem 2.9 that, for any multiset $V$ of $n$ voters in ${\mathbb{R}}^{d}$ , we can compute a point $p$ with $\beta(p,V)\geq 1/\sqrt{d}$ (even with $\beta(p,V)\geq\sqrt{3}/2$ , in the plane). However, a given voter multiset $V$ may admit a $\beta$ -plurality point for larger values of $\beta$ —possibly even for $\beta=1$ . In this section we study the problem of computing a point $p$ that maximizes $\beta(p,V)$ , that is, a point $p$ with $\beta(p,V)=\beta(V)$ .

3.1 An exact algorithm

Below we sketch an exact algorithm to compute $\beta(V)$ together with a point $p$ such that $\beta(p,V)=\beta(V)$ . Our goal is to show that, for constant $d$ , this can be done in polynomial time. We do not make a special effort to optimize the exponent in the running time; it may be possible to speed up the algorithm, but it seems clear that it will remain impractical, because of the asymptotic running time, and also because of algebraic issues.

Note that we can efficiently check whether a true plurality point exists (i.e., $\beta=1$ can be achieved) in time $O(n\log n)$ by an algorithm of De Berg et al. [4], and if so, identify this point. Therefore, hereafter $\beta=1$ is used as a sentinel value, and our algorithm proceeds on the assumption that $\beta(p,V)<1$ for any point $p$ .

For a voter $v\in V$ , a candidate $p\in{\mathbb{R}}^{d}$ , and an alternative candidate $q\in{\mathbb{R}}^{d}$ , define $f_{v}(p,q)\coloneqq\min(|qv|/|pv|,1)$ when $p\neq v$ , and define $f_{v}(p,q)\coloneqq 1$ otherwise. Observe that for $f_{v}(p,q)<1$ we have

•

$q$ wins voter $v$ over $p$ if and only if $\beta>f_{v}(p,q)$ ,
•

$q$ and $p$ have a tie over voter $v$ if and only if $\beta=f_{v}(p,q)$ , and
•

$p$ wins voter $v$ over $q$ if and only if $\beta<f_{v}(p,q)$ .

For $f_{v}(p,q)=1$ this is not quite true: when $p=q=v$ we always have a tie, and when $|pv|<|qv|$ then $p$ wins $v$ even when $\beta=f_{v}(p,q)=1$ . When $p=q$ there is a tie for all voters, so the final conclusion (namely that $\left|V[p\succ_{\beta}q]\right|\geqslant\left|V[p\prec_{\beta}q]\right|$ ) is still correct. The fact that we incorrectly conclude that there is a tie when $|pv|<|qv|$ and $\beta=f_{v}(p,q)=1$ does not present a problem either, since we assume $\beta(p,V)<1$ . Hence, we can pretend that checking if $\beta>f_{v}(p,q)$ , or $\beta=f_{v}(p,q)$ , or $\beta<f_{v}(p,q)$ tells us whether $q$ wins $v$ , or there’s a tie, or $p$ wins $v$ , respectively.

Hereafter we identify $f_{v}\colon{\mathbb{R}}^{2d}\to{\mathbb{R}}$ with its graph $\{(p,q,f_{v}(p,q))\}\subset{\mathbb{R}}^{2d+1}$ , which is a $d$ -dimensional surface. Let $f_{v}^{+}$ be the set of points lying above this graph, and $f_{v}^{-}$ be the set of points lying below it. Thus $f_{v}^{+}$ is precisely the set of combinations of $(p,q,\beta)$ where $q$ wins $v$ over $p$ , while $f_{v}$ is the set where $p$ ties with $q$ , and $f_{v}^{-}$ is the set where $q$ loses $v$ to $p$ . Consider the arrangement $\mathcal{A}\coloneqq\mathcal{A}(F)$ defined by the set of surfaces $F\coloneqq\{f_{v}:v\in V\}$ . Each face $C$ in $\mathcal{A}$ is a maximal connected set of points with the property that all points of $C$ are contained in, lie below, or lie above, the same subset of surfaces of $F$ . (Note that we consider faces of all dimensions, not just full-dimensional cells.) Thus for all $(p,q,\beta)\in C$ , exactly one of the following holds: $\left|V[p\succ_{\beta}q]\right|<\left|V[p\prec_{\beta}q]\right|$ , or $\left|V[p\succ_{\beta}q]\right|=\left|V[p\prec_{\beta}q]\right|$ , or $\left|V[p\succ_{\beta}q]\right|>\left|V[p\prec_{\beta}q]\right|$ . Let $L$ be the union of all faces $C$ of $\mathcal{A}(F)$ such that $\left|V[p\succ_{\beta}q]\right|<\left|V[p\prec_{\beta}q]\right|$ , that is, such that $p$ loses against $q$ for all $(p,q,\beta)$ in $C$ . We can construct $\mathcal{A}$ and $L$ in time $O(n^{2d+1})$ using standard machinery, as $\mathcal{A}$ is an arrangement of degree-4 semi-algebraic surfaces of constant description complexity [3, 2]. We are interested in the set

W\coloneqq\{(p,\beta):\left|V[p\succ_{\beta}q]\right|\geqslant\left|V[p\prec_{\beta}q]\right|\mbox{for any competitor $q$ }\}\subset{\mathbb{R}}^{d+1}.

What is the relationship between $W$ and $L$ ? A point $(p,\beta)$ is in $W$ precisely when, for every choice of $q\in{\mathbb{R}}^{d}$ , $p$ wins at least as many voters as $q$ (for the given $\beta$ ). In other words,

W=\{(p,\beta)\mid\text{there is no $q$ such that $(p,q,\beta)\in L$}\}.

That is, $W$ is the complement of the projection of $L$ to the space ${\mathbb{R}}^{d+1}$ representing the pairs $(p,\beta)$ . The most straightforward way to implement the projection would involve constructing semi-algebraic formulas describing individual faces and invoking quantifier elimination on the resulting formulas [2]. Below we outline a more obviously polynomial-time alternative.

Construct the vertical decomposition $\operatorname{vd}(\mathcal{A})$ of $\mathcal{A}$ , which is a refinement of $\mathcal{A}$ into pieces (“subfaces” $\tau$ ), each bounded by at most $2(2d+1)$ surfaces of constant degree and therefore of constant complexity; see Appendix A. A vertical decomposition is specified by ordering the coordinates—we put the coordinates corresponding to $q$ last. Since $\operatorname{vd}(\mathcal{A})$ is a refinement of $\mathcal{A}$ , the set $L$ is the union of subfaces $\tau$ of $\operatorname{vd}(\mathcal{A})$ fully contained in $L$ . Since $\mathcal{A}$ is an arrangement of $n$ well-behaved surfaces in $2d+1\geqslant 5$ dimensions, the complexity of $\operatorname{vd}(\mathcal{A})$ is $O(n^{2(2d+1)-4+\varepsilon})=O(n^{4d-2+\varepsilon})$ , for any $\varepsilon>0$ [21]. In particular, $L$ comprises $\ell\coloneqq O(n^{4d-2+\varepsilon})$ subfaces.

Since each $\tau\subset L$ is a subface of the vertical decomposition $\operatorname{vd}(\mathcal{A})$ in which the last $d$ coordinates correspond to $q$ , the projection $\tau^{\prime}$ of $\tau$ to ${\mathbb{R}}^{d+1}$ is easy obtain (see Appendix A) in constant time; indeed it can be obtained by discarding the constraints on these last $d$ coordinates from the description of $\tau$ . Thus, in time $O(\ell)$ we can construct the family of all the projections of the $\ell$ subfaces of $L$ , each a constant-complexity semi-algebraic object in ${\mathbb{R}}^{d+1}$ . We now construct the arrangement $\mathcal{A}^{\prime}$ of the resulting collection and its vertical decomposition $\operatorname{vd}(\mathcal{A}^{\prime})$ . The complexity of $\operatorname{vd}(\mathcal{A}^{\prime})$ is either $O(\ell^{d+1+\varepsilon})$ or $O(\ell^{2(d+1)-4+\varepsilon})=O(\ell^{2d-2+\varepsilon})$ , depending on whether $d+1\leqslant 4$ or not, respectively [21]. Each subface in $\operatorname{vd}(\mathcal{A}^{\prime})$ is either fully contained in the projection of $L$ or fully disjoint from it. Collecting all of the latter subfaces, we obtain a representation of $W$ as a union of at most $O(\ell^{O(d)})=O(n^{O(d^{2})})$ constant-complexity semi-algebraic objects.

Now if $(p,\beta)\in W$ is the point with the highest value of $\beta$ , then $\beta(V)=\beta(p,V)=\beta$ . It can be found by enumerating all the subfaces of $\operatorname{vd}(\mathcal{A}^{\prime})$ contained in the closure of $W$ —we take the closure because $V(p,\beta)$ is defined as a supremum—and identifying their topmost point or points. Since each face has constant complexity, this can be done in $O(1)$ time per subface.⁵⁵5Once again, the projection to the $\beta$ coordinate is particularly easy to obtain if, when constructing $\operatorname{vd}(A^{\prime})$ , we set the coordinate corresponding to $\beta$ first. This completes our description of an $O(n^{O(d^{2})})$ -time algorithm to compute the best $\beta$ that can be achieved for a given set of voters $V$ , and the candidate $p$ (or the set of candidates) that achieve this value.

3.2 An approximation algorithm

Since computing $\beta(V)$ exactly appears expensive, we now turn our attention to approximation algorithms. In particular, given a voter set $V$ in ${\mathbb{R}}^{d}$ and an $\varepsilon\in(0,1/2]$ , we wish to compute a point $\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu$ such that $\beta(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu,V)\geqslant(1-\varepsilon)\cdot\beta(V)$ .

Our approximation algorithm works in two steps. In the first step, we compute a set $P$ of $O(n/\varepsilon^{2d-1}\log(1/\varepsilon))$ candidates. $P$ may not contain the true optimal point $p$ , but we will ensure that $P$ contains a point $\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu$ such that $\beta(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu,V)\geqslant(1-\varepsilon/2)\cdot\beta(V)$ . In the second step, we approximate $\beta(p^{\prime},V)$ for each $p^{\prime}\in P$ , to find an approximately best candidate.

Constructing the candidate set $P$ .

To construct the candidate set $P$ , we will generate, for each voter $v_{i}\in V$ , a set $P_{i}$ of $O(1/\varepsilon^{2d-1}\log(1/\varepsilon))$ candidate points. Our final set $P$ of candidates will be the union of the sets $P_{1},\ldots,P_{n}$ . Next we describe how to construct $P_{i}$ .

Partition ${\mathbb{R}}^{d}$ into a set $\mathcal{C}$ of $O(1/\varepsilon^{d-1})$ simplicial cones with apex at $v_{i}$ and opening angle $\varepsilon/(2\sqrt{d})$ , so that for every pair of points $u$ and $u^{\prime}$ in the same cone we have $\angle uv_{i}u^{\prime}\leqslant\varepsilon/(2\sqrt{d})$ . We assume for simplicity (and can easily guarantee) that no voter in $V$ lies on the boundary of any of the cones, except for $v_{i}$ itself and any voters coinciding with $v_{i}$ . Let $\mathcal{C}(v_{i})$ denote the set of all cones in $\mathcal{C}$ whose interior contains at least one voter. For each cone $C\in\mathcal{C}(v_{i})$ we generate a candidate set $G_{i}(C)$ as explained next, and then we set $P_{i}\coloneqq\bigcup_{C\in\mathcal{C}(v_{i})}G_{i}(C)\cup\{v_{i}\}$ .

Let $d_{C}$ be the distance from $v_{i}$ to the nearest other voter (not coinciding with $v_{i}$ ) in $C$ . Let $A_{i}(C)$ be the closed spherical shell defined by the two spheres of radii $\varepsilon\cdot d_{C}$ and $d_{C}/\varepsilon$ around $v_{i}$ , as shown in Fig. 8(i). The open ball of radius $\varepsilon\cdot d_{C}$ is denoted by $A_{i}^{\mathrm{in}}(C)$ , and the complement of the closed ball of radius $d_{C}/\varepsilon$ is denoted by $A_{i}^{\mathrm{out}}(C)$ . Let $G_{i}(C)$ be the vertices in an exponential grid defined by a collection of spheres centered at $v_{i}$ , and the extreme rays of the cones in $\mathcal{C}$ ; see Fig. 8(ii). The spheres have radii $(1+\varepsilon/4)^{i}\cdot\varepsilon\cdot d_{C}$ , for $0\leqslant i\leqslant\log_{(1+\varepsilon/4)}(1/\varepsilon^{2})=O((1/\varepsilon)\log(1/\varepsilon))$ . Observe that $G_{i}(C)$ contains not only points in $C$ , but in the entire spherical shell $A_{i}(C)$ . The set $G_{i}(C)$ consists of $O(1/\varepsilon^{d}\log(1/\varepsilon))$ points, and it has the following property:

Let $p$ be any point in the spherical shell $A_{i}(C)$ , and let $p^{\prime}$ be a corner of the grid cell containing $p$ and nearest to $p$ . Then $|p^{\prime}p|\leqslant\varepsilon\cdot|pv_{i}|$ . $(\ast)$

To prove the property, let $q$ be the point on $pv_{i}$ such that $|qv_{i}|=|p^{\prime}v_{i}|$ . From the construction of the exponential grid we have $|pq|\leqslant\frac{\varepsilon}{4}\cdot|pv_{i}|$ . Since $p^{\prime}$ and $q$ lie in the same cone $\angle p^{\prime}v_{i}q\leqslant\frac{\varepsilon}{2\sqrt{d}}$ and, consequently, $|p^{\prime}q|\leqslant\frac{\varepsilon}{2}\cdot|qv_{i}|\leqslant(1+\frac{\varepsilon}{4})\cdot\frac{\varepsilon}{2}\cdot|pv_{i}|$ . The property is now immediate since $|pp^{\prime}|\leqslant|pq|+|qp^{\prime}|<\varepsilon\cdot|pv_{i}|$ .

As mentioned above, $P_{i}\coloneqq\bigcup_{C\in\mathcal{C}(v_{i})}G_{i}(C)\cup\{v_{i}\}$ , and the final candidate set $P$ is defined as $P\coloneqq\bigcup_{v_{i}\in V}P_{i}$ . Computing the sets $P_{i}$ is easy: for each of the $O(1/\varepsilon^{d-1})$ cones $C\in\mathcal{C}(v_{i})$ , determine the nearest neighbor of $v_{i}$ in $C$ in $O(n)$ time by brute force, and then generate $G_{i}(C)$ in $O((1/\varepsilon^{(d-1)})\log(1/\varepsilon))$ time. (It is not hard to speed up the nearest-neighbor computation using appropriate data structures, but this will not improve the final running time in Theorem 3.6.) We obtain the following lemma.

Lemma 3.1.

The candidate set $P$ has size $O(n/\varepsilon^{2d-1}\log(1/\varepsilon))$ and can be constructed in $O(n^{2}/\varepsilon^{d-1}+n/\varepsilon^{2d-1}\log(1/\varepsilon))$ time.

The next lemma is crucial to show that $P$ is a good candidate set.

Lemma 3.2.

For any point $p\in{\mathbb{R}}^{d}$ , there exists a point $p^{\prime}\in P$ with the following property: for any voter $v_{j}\in V$ , we have that $|p^{\prime}v_{j}|\leqslant(1+2\varepsilon)\cdot|pv_{j}|$ .

Proof 3.3.

Let $v_{i}$ be a voter nearest to $p$ . We will argue that the set $P_{i}$ contains a point $p^{\prime}$ with the desired property. We distinguish three cases.
Case I: There is a cone $C\in\mathcal{C}(v_{i})$ such that $p$ lies in the spherical shell $A_{i}(C)$ . In this case we pick $p^{\prime}$ to be a point of $G_{i}(C)$ nearest to $p$ , that is, $p^{\prime}$ is a corner nearest to $p$ of the grid cell containing $p$ . By property $(\ast)$ we have

|p^{\prime}v_{j}|\leqslant|p^{\prime}p|+|pv_{j}|\leqslant\varepsilon\cdot|pv_{i}|+|pv_{j}|\leqslant(1+\varepsilon)\cdot|pv_{j}|,

where the last inequality follows from the fact that $v_{i}$ is a voter nearest to $p$ .
Case II: Point $p$ lies in $A_{i}^{\mathrm{in}}(C)$ for all $C\in\mathcal{C}(v_{i})$ . In this case we pick $p^{\prime}\coloneqq v_{i}$ . Clearly $|p^{\prime}v_{j}|=0\leqslant(1+\varepsilon)\cdot|pv_{j}|$ for $j=i$ . For $j\neq i$ , we argue as follows. Let $C\in\mathcal{C}(v_{i})$ be the cone containing $v_{j}$ . Since we are in Case II we know that $p\in A_{i}^{\mathrm{in}}(C)$ , and so

|p^{\prime}v_{j}|\leqslant|p^{\prime}p|+|pv_{j}|\leqslant\varepsilon d_{C}+|pv_{j}|\leqslant\varepsilon|p^{\prime}v_{j}|+|pv_{j}|.

(1)

Moreover, we have

|pv_{j}|\geqslant|p^{\prime}v_{j}|-|pp^{\prime}|\geqslant|p^{\prime}v_{j}|-\varepsilon d_{C}\geqslant|p^{\prime}v_{j}|/2,

(2)

where the last step uses that $\varepsilon\leqslant 1/2$ and $d_{C}\leqslant|p^{\prime}v_{j}|$ . Combining (1) and (2), we obtain $|p^{\prime}v_{j}|\leqslant(1+2\varepsilon)\cdot|pv_{j}|$ .
Case III: Cases I and II do not apply.

In this case there is at least one cone $C$ such that $p\in A_{i}^{\mathrm{out}}(C)$ . Of all such cones, let $C^{*}$ be the one whose associated distance $d_{C^{*}}$ is maximized. Let $p^{\prime\prime}$ be the point on the segment $pv_{i}$ at distance $d_{C}/\varepsilon$ from $v_{i}$ . Without loss of generality, we will assume that $p$ and $v_{i}$ only differ in the $x_{d}$ coordinate; see Fig. 9(i).

We will prove that the point $p^{\prime}$ of $G_{i}(C^{*})$ nearest to $p^{\prime\prime}$ (refer to Fig. 9(i)) has the desired property. Consider a voter $v_{j}$ . We distinguish three cases.

•

When $i=j$ , then we have

|p^{\prime}v_{i}|\leqslant|p^{\prime}p^{\prime\prime}|+|p^{\prime\prime}v_{i}|\leqslant(1+\varepsilon)|p^{\prime\prime}v_{i}|\leqslant(1+\varepsilon)|pv_{i}|,

where the second inequality follows from ( $\ast$ ).

•

When $v_{j}$ lies in a cone $C$ such that $p\in A_{i}^{\mathrm{in}}(C)$ , then we can use the same argument as in Case II to show that $|p^{\prime}v_{j}|\leqslant(1+2\varepsilon)\cdot|pv_{j}|$ .

•

In the remaining case $v_{j}$ lies in a cone $C$ such that $p\in A_{i}^{\mathrm{out}}(C)$ . Let $v_{k}$ be a voter in $C$ nearest to $v_{i}$ . Since $|v_{i}v_{k}|=d_{C}$ , $|pv_{i}|\geqslant d_{C}/\varepsilon$ , and $|pv_{k}|\geqslant|pv_{i}|$ , we can deduce that $\angle{pv_{i}v_{k}}\geqslant\pi/2-\varepsilon/2$ , as illustrated in Fig. 9(ii). Furthermore, since $v_{k}$ and $v_{j}$ belong to the same cone $C$ the angle $\angle{v_{k}v_{i}v_{j}}$ is bounded by $\varepsilon/2\sqrt{d}\leqslant\varepsilon/2$ according to the construction. Putting the two angle bounds together we conclude that $\angle{pv_{i}v_{j}}\geqslant\frac{\pi}{2}-\varepsilon$ . Now consider the triangle defined by $p,v_{i}$ and $v_{j}$ . From the Law of Sines we obtain

\frac{|v_{i}v_{j}|}{\sin\angle{v_{i}pv_{j}}}=\frac{|pv_{j}|}{\sin\angle{pv_{i}v_{j}}},\text{\quad or\quad}|v_{i}v_{j}|=|pv_{j}|\cdot\frac{\sin\angle{v_{i}pv_{j}}}{\sin\angle{pv_{i}v_{j}}}\leqslant\frac{|pv_{j}|}{\cos\varepsilon}\leqslant(1+\varepsilon)\cdot|pv_{j}|,

for $\varepsilon<1/2$ . Since $p^{\prime\prime}$ lies on the line between $p$ and $v_{i}$ we have:

|p^{\prime\prime}v_{j}|\leqslant\max\{|pv_{j}|,|v_{i}v_{j}|\}\leqslant(1+\varepsilon)\cdot|pv_{j}|.

Finally we get the claimed bound by noting that $|p^{\prime}p^{\prime\prime}|\leqslant\varepsilon\cdot|p^{\prime}v_{i}|$ (from (*)),

|p^{\prime}v_{j}|\leqslant|p^{\prime}p^{\prime\prime}|+|p^{\prime\prime}v_{j}|\leqslant\varepsilon\cdot|p^{\prime}v_{i}|+(1+\varepsilon)\cdot|pv_{j}|\leqslant(1+2\varepsilon)\cdot|pv_{j}|.

An approximate decision algorithm.

Given a point $p$ , a positive real value $\varepsilon$ and the voter multiset $V$ , we say that an algorithm Alg is an $\varepsilon$ -approximate decision algorithm if

•

Alg answers yes if $p$ is a $\beta$ -plurality point, and
•

Alg answers no if $p$ is not a $(1-\varepsilon)\beta$ -plurality point.

In the remaining cases, where $(1-\varepsilon)\beta<\beta(p,V)<\beta$ , Alg may answer yes or no.

Next we propose an $\varepsilon$ -approximate decision algorithm Alg. The algorithm will use the so-called Balanced Box-Decomposition (BBD) tree introduced by Arya and Mount [1]. BBD trees are hierarchical space-decomposition trees such that each node $\mu$ represents a region in ${\mathbb{R}}^{d}$ , denoted by $\mathrm{region}(\mu)$ , which is a $d$ -dimensional axis-aligned box or the difference of two such boxes. A BBD tree for a set $P$ of $n$ points in ${\mathbb{R}}^{d}$ can be built in $O(n\log n)$ time using $O(n)$ space. It supports $(1+\varepsilon)$ -approximate range counting queries with convex query ranges in $O(\log n+\varepsilon^{1-d})$ time [1]. In our algorithm all query ranges will be balls, hence a $(1+\varepsilon)$ -approximate range-counting query for a $d$ -dimensional ball $s(v,r)$ with center at $v$ and radius $r$ returns an integer $I$ such that $|P\cap s(v,r)|\leqslant I\leqslant|P\cap s(v,(1+\varepsilon)r)|$ .

Our $\varepsilon$ -approximate decision algorithm Alg works as follows.

1.

Construct a set $Q$ of $O(n/\varepsilon^{d-1})$ potential candidates competing against $p$ , as follows. Let $Q(v)$ be a set of $O(1/\varepsilon^{d-1})$ points distributed uniformly on the boundary of the ball $s(v,(1-\varepsilon/2)\cdot\beta\cdot|pv|)$ , such that the distance between any point on the boundary and its nearest neighbor in $Q(v)$ is at most $\frac{\varepsilon}{4\sqrt{d}}\cdot|pv|\leqslant\frac{\varepsilon}{4}\cdot\beta\cdot|pv|$ . In the last step we use the fact that $\beta\geqslant 1/\sqrt{d}$ , according to Lemma 2.3. Set $Q\coloneqq Q(v_{1})\cup\cdots\cup Q(v_{n})$ .
2.

Build a BBD tree $\mathcal{T}$ on $Q$ . Add a counter $c(\mu)$ to each node $\mu$ in $\mathcal{T}$ , initialized to zero.
3.

For each voter $v\in V$ perform a $(1+\varepsilon/4)$ -approximate range-counting query with $s(v,(1-\varepsilon/4)\cdot\beta\cdot|pv|)$ in $\mathcal{T}$ . We modify the search in $\mathcal{T}$ slightly as follows. If an internal node $\mu\in T$ is visited and expanded during the search, then for every non-expanded child $\mu^{\prime}$ of $\mu$ with $\mathrm{region}(\mu^{\prime})$ entirely contained in $s(v,(1+\varepsilon/4)(1-\varepsilon/4)\cdot\beta\cdot|pv|))\subset s(v,\beta\cdot|pv|)$ we increment the counter $c(\mu^{\prime})$ . Similarly, if a leaf is visited then the counter is incremented if the point stored in the leaf lies within $s(v,(1-\varepsilon/4)\cdot\beta\cdot|pv|)$ .
4.

For a leaf $\mu$ in $\mathcal{T}$ , let $M(\mu)$ be the set of nodes in $\mathcal{T}$ on the path from the root to $\mu$ , and let $C(\mu)=\sum_{\mu^{\prime}\in M(\mu)}c(\mu^{\prime})$ . Compute $C(\mu)$ for all leaves $\mu$ in $\mathcal{T}$ by a pre-order traversal of $\mathcal{T}$ , and set $C\coloneqq\max_{\mu}C(\mu)$ .
5.

If $C\leqslant n/2$ , then return yes, otherwise no.

To prove correctness of the algorithm we define, for a given $\gamma>0$ , a fuzzy ball $s_{\gamma}(v,r)$ to be any set such that $s(v,r)\subseteq s_{\gamma}(v,r)\subseteq s(v,(1+\gamma)r)$ . Thus if $q\in s(v,r)$ then $q\in s_{\gamma}(v,r)$ , if $q\not\in s(v,(1+\gamma)r)$ then $q\not\in s_{\gamma}(v,r)$ , and otherwise $q$ may or may not be inside in $s_{\gamma}(v,r)$ . We now observe that for each voter $v_{i}\in V$ there is a fuzzy ball $s_{\varepsilon/4}(v_{1},(1-\varepsilon/4)\cdot\beta\cdot|pv_{i}|)$ such that the value $C(\mu)$ for a leaf $\mu$ storing a point $q$ is the depth of $q$ in the arrangement, denoted by $\mathcal{A}_{\varepsilon/4}(V,1-\varepsilon/4)$ , of the fuzzy balls $s_{\varepsilon/4}(v_{1},(1-\varepsilon/4)\cdot\beta\cdot|pv_{1}|),\ldots,s_{\varepsilon/4}(v_{n},(1-\varepsilon/4)\cdot\beta\cdot|pv|)$ .

Lemma 3.4.

Algorithm Alg $\varepsilon$ -approximately decides if $p$ is a $\beta$ -plurality point in time $O(\frac{n}{\varepsilon^{d-1}}\log\frac{n}{\varepsilon^{d-1}})$ .

Proof 3.5.

We start by analyzing the running time of the algorithm. Constructing the set of points in $Q$ can be done in time linear in $|Q|$ , while building the BBD-tree $\mathcal{T}$ requires $O((n/\varepsilon^{d-1})\log(n/\varepsilon^{d-1}))$ time [1, Lemma 1]. Next, the algorithm performs $n$ approximate range queries, each requiring $O(\log\frac{n}{\varepsilon^{d-1}}+\frac{1}{\varepsilon^{d-1}})$ time [1, Theorem 2]). Note that the small modification we made to the query algorithm to update the counters does not increase the asymptotic running time. Finally, the traversal of $\mathcal{T}$ to compute $C$ takes time linear in the size of $\mathcal{T}$ , which is $O(n/\varepsilon^{d-1})$ .

It remains to prove that Alg is correct.

•

If $p$ is a plurality point there can be no point $q\in{\mathbb{R}}^{d}$ having depth greater than $n/2$ in the arrangement of the balls $s(v_{1},\beta\cdot|pv|),\ldots,s(v_{n},\beta\cdot|pv|)$ . Since $s_{\varepsilon/4}(v,(1-\varepsilon/4)\cdot\beta\cdot|pv|)\subset s(v,\beta\cdot|pv|)$ , for all $v$ , Alg could not have found a point with depth greater than $n/2$ , and hence, must return yes.

•

If $p$ is not a $(1-\varepsilon)\beta$ -plurality point, then there exists a point $q$ with depth greater than $n/2$ in the arrangement $\mathcal{A}(V,1-\varepsilon)$ of the balls $s(v_{1},(1-\varepsilon)\cdot\beta\cdot|pv|),\ldots,s(v_{n},(1-\varepsilon)\cdot\beta\cdot|pv|)$ . Let $q^{\prime}$ be the point in $Q$ nearest to $q$ . We claim that for any ball $s(v,(1-\varepsilon)\cdot\beta\cdot|pv|)$ that contains $q$ , its expanded version $s(v,(1-\varepsilon/4)\cdot\beta\cdot|pv|)$ contains $q^{\prime}$ . Of course, if $s(v,(1-\varepsilon)\cdot\beta\cdot|pv|)$ contains $q^{\prime}$ then we are done. Otherwise, let $x$ be the point where $qq^{\prime}$ intersects the boundary of $s(v,(1-\varepsilon)\cdot\beta\cdot|pv|)$ ; see Fig. 10. Note that $q^{\prime}$ must also be the point in $Q$ nearest to $x$ .

Let $x^{\prime}$ be the point on the boundary of $s(v,(1-\varepsilon/2)\cdot\beta\cdot|pv|)$ nearest to $x$ , and let $q^{\prime\prime}$ be a point in $Q$ on the boundary of $s(v,(1-\varepsilon/2)\cdot\beta\cdot|pv|)$ . By construction, we have

|xx^{\prime}|=\frac{\varepsilon}{4}\cdot\beta\cdot|pv|\quad\textrm{and}\quad|x^{\prime}q^{\prime\prime}|\leqslant\frac{\varepsilon}{4}\cdot\beta\cdot|pv|

and, by the triangle inequality, we obtain

|xq^{\prime}|\leqslant|xq^{\prime\prime}|\leqslant|xx^{\prime}|+|x^{\prime}q^{\prime\prime}|\leqslant\frac{\varepsilon}{2}\cdot\beta\cdot|pv|.

This implies that $s(v,(1-\varepsilon/4)\cdot\beta\cdot|pv|)\subseteq s_{\varepsilon/4}(v,(1-\varepsilon/4)\cdot\beta\cdot|pv|)$ must contain $q^{\prime}$ . Consequently, if $q$ has depth at least $n/2$ in $\mathcal{A}(V,1-\varepsilon)$ then $q^{\prime}$ has depth at least $n/2$ in the arrangement $\mathcal{A}_{\varepsilon/4}(V,(1-\varepsilon/4))$ , and hence, the algorithm will return no.

The algorithm.

Now we have the tools required to approximate $\beta(V)$ . First, generate the set $P$ of $O(\frac{n}{\varepsilon^{2d-1}}\log\frac{1}{\varepsilon})$ candidate points. For each candidate point $p\in P$ , perform a binary search for an approximate $\beta^{*}(p)$ in the interval $[1/\sqrt{d},1]$ , until the remaining search interval has length at most $\varepsilon/2\cdot 1/\sqrt{d}$ . For each $p$ and $\beta^{*}$ , $(\varepsilon/2)$ -approximately decide if $p$ is a $\beta^{*}$ -plurality point in $V$ . Return the largest $\beta^{*}$ and the corresponding point $p$ on which the algorithm says yes.

Theorem 3.6.

Given a multiset $V$ of voters in ${\mathbb{R}}^{d}$ , a $((1-\varepsilon)\cdot\beta(V))$ -plurality point can be computed in $O(\frac{n^{2}}{\varepsilon^{3d-2}}\cdot\log\frac{n}{\varepsilon^{d-1}}\cdot\log^{2}\frac{1}{\varepsilon})$ .

4 Concluding Remarks

We proved that any finite set of voters in ${\mathbb{R}}^{d}$ admits a $\beta$ -plurality point for $\beta=1/\sqrt{d}$ and that some sets require $\beta=\sqrt{3}/2$ . For $d=2$ we managed to close the gap by showing that $\beta^{*}_{2}=\sqrt{3}/2$ . One of the main open problems is to close the gap for $d>2$ . Recall that recently the bounds for $d\geqslant 4$ have been improved—see Footnote 3 in the introduction—but there is still a small gap left between the upper and lower bound.

We also presented an approximation algorithm that finds, for a given $V$ , a $(1-\varepsilon)\cdot\beta(V)$ -plurality point. The algorithm runs in $O^{*}(n^{2}/\varepsilon^{3d-2})$ time. Another open problem is whether a subquadratic approximation algorithm exists, and to prove lower bounds on the time to compute $\beta(V)$ or $\beta(p,V)$ exactly. Finally, it will be interesting to study $\beta$ -plurality points in other metrics, for instance in the personalized $L_{1}$ -metric [4] for $d>2$ or in the $L_{1}$ -metric for $d\geqslant 2$ .

Acknowledgements

The authors would like to thank Sampson Wong for improving an earlier version of Lemma 2.5.

References

[1] Sunil Arya and David M. Mount. Approximate range searching. Computational Geometry – Theory & Applications, 17(3):135–152, 2000.
[2] Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics). Springer-Verlag, Berlin, Heidelberg, 2006.
[3] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008.
[4] Mark de Berg, Joachim Gudmundsson, and Mehran Mehr. Faster algorithms for computing plurality points. ACM Transactions on Algorithms, 14(3), 2018.
[5] Duncan Black. On the rationale of group decision-making. Journal of Political Economy, 56(1):23–34, 1948.
[6] Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete & Computational Geometry, 9:145–158, 1993.
[7] Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir. A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoretical Computer Science, 84:77–105, 1991. Also in Proc. 16th Int. Colloq. on Automata, Languages and Programming, 1989, pp. 179–193.
[8] Jonathan Chung. Optimally locating a new candidate in spatial and valence models of voting games, 2018. Honours thesis, University of Sydney.
[9] Tamal K. Dey. Improved bounds for planar $k$ -sets and related problems. Discrete & Computational Geometry, 19(3):373–382, 1998.
[10] Anthony Downs. An Economic Theory of Political Action in a Democracy. Journal of Political Economy, 65(2):135–135, 1957.
[11] Adrian Dumitrescu, János Pach, and Géza Tóth. Drawing Hamiltonian cycles with no large angles. The Electronic Journal of Combinatorics, 19(2):P31, 2012.
[12] James Enelow and Melvin Hinisch. On Plott’s pairwise symmetry condition for majority rule equilibrium. Public Choice, 40(3):317–321, 1983.
[13] Haldun Evrenk. Valence politics. In Roger D. Congleton, Bernard Grofman, Stefan Voigt, and Haldun Evrenk, editors, Oxford Handbook of Public Choice, chapter 13. Oxford University Press, 2019.
[14] Scott Feld, Bernard Grofman, and Nicholas Miller. Centripetal forces in spatial voting: On the size of the yolk. Public Choice, 59:37–50, 10 1988.
[15] Arnold Filtser and Omrit Filtser. Plurality in spatial voting games with constant $\beta$ . Manuscript, 2020.
[16] Noah Giansiracusa and Cameron Ricciardi. Computational geometry and the U.S. supreme court. Math. Soc. Sci., 98:1–9, 2019.
[17] Fabian Gouret, Guillaume Hollard, and Stéphane Rossignol. An empirical analysis of valence in electoral competition. Social Choice and Welfare, 37(2):309–340, 2011.
[18] Joachim Gudmundsson and Sampson Wong. Computing the yolk in spatial voting games without computing median lines. In The 33rd AAAI Conference on Artificial Intelligence, pages 2012–2019. AAAI Press, 2019.
[19] Helios Herrera, David K. Levine, and César Martinelli. Policy platforms, campaign spending and voter participation. Journal of Public Economics, 92(3):501–513, 2008.
[20] Guillaume Hollard and Stéphane Rossignol. An alternative approach to valence advantage in spatial competition. Journal of Public Economic Theory, 10(3):441–454, 2008.
[21] Vladlen Koltun. Almost tight upper bounds for vertical decompositions in four dimensions. Journal of the ACM, 51(5):699–730, 2004.
[22] Richard D. McKelvey. Covering, dominance, and institution-free properties of social choice. American Journal of Political Science, 30(2):283–314, 1986.
[23] Nicholas R. Miller. The spatial model of social choice and voting. In Jac C. Heckelman and Nicholas R. Miller, editors, Handbook of Social Choice and Voting, chapter 10, pages 163–181. Edward Elgar Publishing, 2015.
[24] Charles R. Plott. A notion of equilibrium and its possibility under majority rule. The American Economic Review, 57(4):787–806, 1967.
[25] David Sanders, Harold D. Clarke, Marianne C. Stewart, and Paul Whiteley. Downs, stokes and the dynamics of electoral choice. British Journal of Political Science, 41(2):287–314, 2011.
[26] Micha Sharir and Pankaj K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, 1995.
[27] Donald E. Stokes. Spatial models of party competition. American Political Science Review, 57(2):368–377, 1963.
[28] Alan E. Wiseman. A theory of partisan support and entry deterrence in electoral competition. Journal of Theoretical Politics, 18(2):123–158, 2006.
[29] Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang, and Kun-Mao Chao. Computing plurality points and condorcet points in Euclidean space. In Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC), volume 8283 of Lecture Notes in Computer Science, pages 688–698. Springer, 2013.

Appendix

Appendix A A primer on vertical decompositions

We follow the notation and terminology of [26, 7]. A vertical decomposition is, roughly, any partition of space into finitely many so-called cylindrical cells (see below for a definition); it need not be a topological complex. A vertical decomposition of an arrangement is a refinement of an arrangement into cylindrical cells,⁶⁶6The specific decomposition depends on the algorithm used to construct it and on the ordering of the coordinates. In the computational- and combinatorial-geometry literature, one often speaks of “the vertical decomposition of the arrangement” in the sense of “the vertical decomposition obtained by applying the algorithm, say, of Chazelle et al.[7] or of Koltun [21], to the given arrangement.” where refinement means that each cylindrical cell is a subset of a face in the arrangement. We define cylindrical cells recursively. To simplify the notation, any inequality limit in our definitions can be omitted, i.e., replaced by a $\pm\infty$ , as appropriate. For example, when we talk about an open interval $(a,b)$ , i.e., the set of numbers $x$ with $a<x<b$ , we include the possibilities of the unbounded intervals $(-\infty,b)$ , $(a,+\infty)$ , and $(-\infty,+\infty)$ .

A one-dimensional cylindrical cell is either a singleton or an open interval $(a,b)$ . So a one-dimensional vertical decomposition is a decomposition of ${\mathbb{R}}$ into a finite number of singletons and intervals.

We now define a cylindrical cell $\tau$ in ${\mathbb{R}}^{2}$ . Its projection $\tau^{\prime}$ to the $x_{1}$ -axis is a cylindrical cell in ${\mathbb{R}}$ . The cell $\tau$ must have one of the following two forms:

•

$\{(x_{1},f_{2}(x_{1}))\mid x_{1}\in\tau^{\prime}\}$ , where $f_{2}:\tau^{\prime}\to{\mathbb{R}}$ is a continuous total function, or
•

$\{(x_{1},x_{2})\mid x_{1}\in\tau^{\prime},f_{2}(x_{1})<x_{2}<g_{2}(x_{1})\}$ , where $f_{2},g_{2}:\tau^{\prime}\to{\mathbb{R}}$ are two continuous total functions, with the property that $f_{2}(x_{1})<g_{2}(x_{1})$ for all $x_{1}\in\tau^{\prime}$ .

If $\tau^{\prime}$ is a singleton, the former defines a vertex and the latter an (open) vertical segment. If $\tau^{\prime}$ is an interval, the former defines an open monotone arc (a portion of the graph of the function $f_{2}$ ) and the latter an open pseudo-trapezoid delimited by two (possibly degenerate) vertical segments on left and right and by the two disjoint function graphs below and above. (Recall that any of the limits may be omitted. For example, ${\mathbb{R}}^{2}$ is a legal cell in a trivial two-dimensional vertical decomposition consisting only of itself, where all the limits have been “replaced by infinities.”)

A cylindrical cell $\tau\subset{\mathbb{R}}^{d}$ is defined recursively. Its projection $\tau^{\prime}$ is a cylindrical cell in ${\mathbb{R}}^{d-1}$ . Moreover, $\tau$ must have one of the following forms:

•

$\{(x^{\prime},f_{d}(x_{1},\dots,x_{d-1}))\mid x^{\prime}\in\tau^{\prime}\}$ , where $f_{d}:\tau^{\prime}\to{\mathbb{R}}$ is a continuous total function, or
•

$\{(x^{\prime},x_{d})\mid x^{\prime}\in\tau^{\prime},f_{d}(x^{\prime})<x_{d}<g_{d}(x^{\prime})\}$ , where $f_{d},g_{d}:\tau^{\prime}\to{\mathbb{R}}$ are two continuous total functions, with the property that $f_{d}(x^{\prime})<g_{d}(x^{\prime})$ for all $x^{\prime}\in\tau^{\prime}$ .

A cylindrical cell is fully specified by giving its dimension and the sequence of functions $f_{i}$ or pairs of functions $f_{i},g_{i}$ , as appropriate. In particular, the projection of the cell in a $k$ -dimensional decomposition to its first $k^{\prime}<k$ coordinates can be obtained by retaining the inequalities in the first $k^{\prime}$ coordinates and discarding the remaining ones.

On β\beta-Plurality Points in Spatial Voting Games