I have a set of simple, non-overlapping polygons and I want to find all bitangent lines.
A bitangent line is defined as a line by two vertices such that the two incident edges are on the same side of the line, in pairs. A single polygon can also have bitangents.
All bitangent lines to a set of polygons can easily be found by brute force: consider all pairs of vertices ($O(n^2$) of them) and check if the other endpoints of the incident edges are on the same side of the line they define.
I wonder if a faster solution can be found. Has any algorithm been published on this problem ?
Additional question: is my terminology correct ?
Update:
I forgot to mention that the bitangents are allowed to cross the polygons (except at the tangency vertices). I have updated the figure to show this possibility.
I am not sure if the simplicity of the polygon helps (bitangency actually remains defined for independent pairs of edges), but it can be used.
[See the OP's comment below; I misread the question, but this still may be useful, so I'll leave it up.]
A key search term here is the visibility complex. Pocchiola & Vegter have written several papers on the topic. This is probably the best place to start.
They specialize to a set of convex objects, and substantially improve the naive algorithms to run in $O(n \log n)$ plus output size.