4
$\begingroup$

I have the following problem:

There are existing stars (as in graph-theory stars) with a fixed representation in a 2D coordinate space, meaning that angles between the edges are not allowed to change.

Now I want to add additional edges from the star center. Both the amount of existing edges and the amount of edges to add can vary.

How can the new edges be added in a way that maximizes the smallest angle between edges in the resulting star? For this minimization, the angles between newly added edges, as well as the angles between newly added and existing edges are relevant.

Here are two trivial examples, the black edges are the existing ones, the blue ones the newly added:

enter image description here

However, there could also be more complex examples, consider adding a different amount of edges(1,2,3,..) to this star:

enter image description here

Ideally, the algorithm is fast and easy to implement in object-oriented programming languages.

Background:
The underlying use case is drawing of Hydrogens for 2D Molecule depictions. In a software, a 2D molecule depiction might be loaded from a file or even drawn by a user, then, the user can trigger an action, adding missing Hydrogen atoms to all existing atoms.
For each atom (star), a varying number of hydrogens depending on the atom type and charge (usually 1-3), should be added and drawn in a visually pleasing way.

The existing edges and angles can not be modified, because they are given by the user. Small angles tend to look bad, therefore, the goal is to maximize the smallest angle.

Currently, this is done by choosing the largest angle, then adding an edge in the middle. Then repeating this until no more edges are to be added. This is very fast and looks reasonably well, but obviously doesn't always find the best solution.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much for the suggestion. I added the underlying use case. The problem formulation is actually original. I tried to find an abstract formulation for my problem. $\endgroup$ – Thomas Kainrad Feb 6 at 20:54
  • 1
    $\begingroup$ It is cool to see an original problem coming from real life! Thanks for the great question. $\endgroup$ – Apass.Jack Feb 6 at 22:18
3
$\begingroup$

Here is an algorithm that simulates the process of adding the edges one by one, keeping the smallest angle between all adjacent edges as largest as possible at all times.

  1. List all $m$ existing edges clockwise as $e_0, e_2, \cdots, e_{m-1}, e_{m}=e_1$.
  2. Create an empty priority queue $P$ for elements of the form $(i, \alpha, j)$ with associated priority $\dfrac\alpha{i+1}$.
  3. For each $0\le j\lt m$, insert $(0, \alpha_j, j)$ into $P$, where $\alpha_j$ is the measure of the angle between edge $e_j$ and $e_{j+1}$. The first number, which is 0 for now, means the number of edges that will be added evenly-spaced between $e_j$ and $e_{j+1}$.
  4. Repeat the following procedure $n$ times, where $n$ is the number of edges to be added.
    • Select the top element $T=(i,\alpha,\_)$ of the priority queue.
    • Add 1 to $i$, which lowers the priority of $T$.
    • Remove and insert $T$ so as to keep $P$ a valid priority queue. (These two operations together can be implemented more efficiently without actually removing $T$ first.)

At the end of algorithm, all elements in $P$ tell us how many edges should be added to each pair of adjacent edges evenly.

Most popular languages have built-in support for priority queues. For example, there is a heapq in Python. There is a PriorityQueue in Java.

$\endgroup$
  • $\begingroup$ This is great and also feels very intuitive. Thanks a lot for the work and the detailed description! $\endgroup$ – Thomas Kainrad Feb 7 at 8:35
4
$\begingroup$

I'll describe an efficient algorithm for this problem.

Suppose we have an angle $\theta$, and we want to find out how many new edges we can add, with the constraint that the minimum angle between all pairs of edges must be at least $\theta$. Then it's not too hard to compute this. Pick any adjacent pair of existing edges; suppose they are at angle $\gamma$ from each other. Then you can add $\lfloor \gamma/\theta \rfloor - 1$ new edges between them, while ensuring the minimum angle remains at least $\theta$. So, sort all of the existing edges by angle, iterate through each pair of adjacent existing angles, count how many new edges you can add between them (using the formula in the previous sentence), and add them up. That tells you how many new edges you can add, if you want the minimum angle between edges to be at least $\theta$.

Great. But in your situation, we don't know $\theta$; we just know that we want to add at least $n$ new edges. So, use binary search on $\theta$ to find the largest $\theta$ such that you can add at least $n$ new edges while preserving a minimum angle of at least $\theta$. You can do this by choosing a value of $\theta$, computing how many new edges you can add (using the algorithm of the previous paragraph), then increasing or decreasing $\theta$ according to the rules of binary search based on whether the number of new edges you could add was above or below $n$.

$\endgroup$
  • $\begingroup$ Thank you very much for this answer. While trying to formulate what I do not like about this approach, I grew more and more fond of it. I am not yet completely sure about its performance, and whether its fast enough for our use case. Therefore, I will leave the question open for some time. If no one posts a more efficient solution or this turns out to be very fast anyways, I will set this as the accepted answer. $\endgroup$ – Thomas Kainrad Feb 6 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.