Processing weighted points of interest. Is there a name for this task/algorithm?
Solution to your algorithm problem

There's a simple solution to your algorithmic problem.  Treat the $a_0,a_1,\dots,a_{k-1}$ as a probability distribution.  Apply kernel smoothing to turn this into a smooth probability distribution.  At this point, you have a probability density function (pdf).  Now compute a cumulative density function (cdf), and find the $n+1$ quartiles of the cdf.  These endpoints of your new bins.

This is "optimal", in the sense that given all of the information available to you, it gives the optimal bin-sizing for a particular distribution.  We could prove this by proving that for a particular pdf, this definition of bins ensures that each bin has exactly $1/n$ probability mass falling within it.

Other approaches to your computer vision task

The Hough transform might not be optimal.  There are other approaches you could also try.  For instance, there are algorithms for detecting lines that are approximately horizontal.  So, the following approach might be better:


Find one long line and approximately find its angle.
Rotate the image so that it is approximately horizontal (since the lines are all approximately parallel, that means all the lines will now be approximately horizontal).
Find all long, approximately-horizontal lines.


The problem of finding long, approximately-horizontal lines has been studied in the literature on image processing and deskewing scanned documents.  Or, if you want a free tool, take a look at existing tools, e.g., Leptonica, pagetools, ImageMagick (convert -deskew), and others.

Another standard approach is to apply the Hough transform twice:


First use the Hough transform to get a rough estimate of the angle.  For instance, you might sweep over some range of possible angles, sensitive to 1 degree or 0.1 degree increments.
Then, use a second Hough transform to get a rough estimate of the angle.  Now you have a much narrower range of possible angles (1 degree or 0.1 degree wide); do the Hough transform over this narrower range, sensitive to 0.01 degree increments (say).


This is more efficient then doing a single Hough transform sensitive to 0.01 degree increments.