  We study the complexity of determining a winning committee under the
Chamberlin--Courant voting rule when voters' preferences are single-crossing on
a line, or, more generally, on a median graph (this class of graphs includes,
e.g., trees and grids). For the line, Skowron et al. (2015) describe an
$O(n^2mk)$ algorithm (where $n$, $m$, $k$ are the number of voters, the number
of candidates and the committee size, respectively); we show that a simple
tweak improves the time complexity to $O(nmk)$. We then improve this bound for
$k=\Omega(\log n)$ by reducing our problem to the $k$-link path problem for
DAGs with concave Monge weights, obtaining a $nm2^{O\left(\sqrt{\log k\log\log
n}\right)}$ algorithm for the general case and a nearly linear algorithm for
the Borda misrepresentation function. For trees, we point out an issue with the
algorithm proposed by Clearwater, Puppe and Slinko (2015), and develop a
$O(nmk)$ algorithm for this case as well. For grids, we formulate a conjecture
about the structure of optimal solutions, and describe a polynomial-time
algorithm that finds a winning committee if this conjecture is true; we also
explain how to convert this algorithm into a bicriterial approximation
algorithm whose correctness does not depend on the conjecture.
