This paper considers a set $S$ of $n$ points, and looks at optimal and approximation algorithms for smallest $k$-enclosing circle and smallest $k$-enclosing square centered on a line segment $\ell$. This paper presents a $O(n\log^2k +n \log n)$ and a $O(n \log n)$ expected time 2-approximation algorithm for smallest $k$-enclosing circle and square (respectively) centered on $\ell$. We also present an exact algorithm that runs in $O(k(n-k)\log^2 n + n\log^2 n+V(n,k))$ expected time where $V(n,k)$ is the time to construct a $k$th order Voronoi diagram.