Stuart P. Lloyd1923–2007
Lloyd's algorithm, 1957
American engineer at Bell Labs who in 1957 devised the method, now called Lloyd's algorithm, of moving points to the middles of their Voronoi cells until they spread evenly. It was published in 1982.
Stipple and Single Line
Thousands of dots, crowded where the picture is dark, nudge themselves apart until they settle like a hand-stippled print. Joined by one line that never crosses itself, they become a drawing in a single stroke.
About this pattern
Stuart Lloyd, 1957 · Adrian Secord, 2002 · Craig S. Kaplan and Robert Bosch, 2005
Stippling is drawing with dots: an engraver or illustrator builds up shade by putting dots closer together where it is dark and further apart where it is light. A computer can do it with a lovely trick. Scatter the dots at random, more of them where the picture is dark. Then give every dot the patch of paper that is nearer to it than to any other dot, its Voronoi cell, and move each dot to the middle of its patch, counting the dark parts more heavily.
Repeat, and the clumps and holes of the random scatter even out until the dots sit in a calm, regular grain, like a stippled print. Moving points to the middles of their cells is Lloyd's algorithm, which Stuart Lloyd of Bell Labs devised in 1957; weighting it by a picture's darkness is Adrian Secord's weighted Voronoi stippling, from 2002.
Then the second trick. Treat the dots as cities and find a short round trip that visits every one, the travelling salesman's problem, and draw the route: one continuous line, which never crosses itself, filling in the picture as it goes. Robert Bosch and Craig Kaplan called it TSP art, and it is a favourite with pen plotters, since the pen goes down once and lifts once.
The route here is found quickly rather than perfectly, starting from the nearest dot each time and then untangling any crossing it finds. The pictures are built in, a lit sphere, a crescent moon, hills and ripples.
In motion the dots shake loose into their first random scatter and settle again; the single line draws itself from start to finish.
Behind the mathematics
Adrian Secord
Weighted Voronoi stippling, 2002
Computer scientist whose 2002 paper Weighted Voronoi Stippling weighted Lloyd's algorithm by an image's darkness, so that dots settle into a stippled picture.
Craig S. Kaplan
TSP Art, with Robert Bosch, 2005
Canadian computer scientist whose research joins geometry, computation and ornamental design, including the proof and visualisation of the hat monotile.
Robert Bosch
TSP Art, with Craig S. Kaplan, 2005
American mathematician who draws pictures with solutions to the travelling salesman problem, and with Craig S. Kaplan wrote TSP Art, Bridges 2005.
Georgy Voronoy1868–1908
The cells each dot settles into
Ukrainian mathematician whose nearest-point decomposition now appears across geometry, crystallography, ecology and computational design.