Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm (Q1126660)

The authors note that in adapting grids to holes in surfaces, it is of great advantage to compute separate grids around each hole. In order to obtain best situated domains, they compute a generalized Voronoi diagram, i.e., they decompose the given surface into parts such that each point not on the boundary of the parts is closest to one given hole. An algorithm to do this by computing selected perpendicular bisectors of couples of points on the boundary curves of different holes is described. The second problem attacked then is the generation of a grid in one Voronoi domain adapted to the shape of the hole. Examples are given and some problems still to be solved to make the algorithm more efficient are indicated.