A portrait drawing robot using a geometric graph approach: Furthest Neighbour Theta-graphs

We examine the problem of estimating ideal edges joining points in a pixel reduction image for an existing point-to-point portrait drawing humanoid robot, Betty. To solve this line drawing problem we present a modified Theta-graph, called Furthest Neighbour Theta-graph, which we show is computable in O(n(log n)/θ) time, where θ is a fixed angle in the graph´s definition. Our results show that the number of edges in the resulting drawing is significantly reduced without degrading the detail of the final output image.