Turning a simple polygon with holes into exterior-bounded only

I am converting cartographic objects, which have an exterior boundary (simple polygon) and zero or more interior boundaries (also simple), into a less sophisticated format that specifies exterior boundary only. To overcome this restriction, I plan to “cut through the body of the shape” — joining a pair of nodes of exterior and interior boundary (see figure, left), thus creating a zero-width way into the shape's former interior space that will then technically become exterior (see figure, right).

So the question is: which nodes to join? (Not that it's unacceptable to create new nodes in suitable locations, but undesirable.) An obvious and ideal choice would be the two nodes most close to each other; moreover, I suppose that those would automatically constitute a valid solution — i. e. the new segments won't intersect any existing one. Consequently, the question becomes: how to find the closest node pair?

Googling on this topic yields many results for similar questions which vary in degree of “similarity”, complexity of understanding the algorithm and computational complexity. But most importantly, as far as I noticed, they vary in applicability to input data, — that is, some are designed for convex polygons only, others fail on “overlapping” polygons (I suppose that includes my case, too). So I decided to ask: which algorithms are optimal or at least suitable for my particular task?

The closest vertices between the inner and outer polygons do not necessarily produce a valid solution as shown in the following figure:

You just need to find a pair of vertices between the inner and outer polygons whose corresponding edge does not intersect either polygon.
Search for vertices $u$ and $v$ from the inner and outer polygons such that the edge $(u,v)$ does not cross any other edge (some care needs to be taken that you don't
slip between two edges as shown on the right above -- choosing the closer vertex avoids this problem).

A straight forward approach would scan all such $u,$ $v,$ and all edges
resulting in $O(n^3)$ time in the worst case -- in practice you'll find a solution fairly quickly. This can be sped up by placing all the vertices in a BSP tree whose half-spaces are defined by the polygon edges -- then you only considering vertices $v$ in the same half-space as $u.$

StackExchange Computer Science Q#43758, answer score: 4