Professor Bender’s Kissing Goodbye Algorithm

“Given a rectangular room with n people in it, what is the most efficient way for each pair of people to kiss each other goodbye?“

Professor Bender, (pictured, of the Department of Computer Science, Stony Brook University, New York) along with his colleagues Ritwik Bose, Rezaul Chowdhury and Samuel McCauley, have made progress towards an answer. Their paper, presented as a chapter in Fun with Algorithms, Lecture Notes in Computer Science, Volume 7288, 2012, pp 28-39 is entitled : ‘The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye‘

It provides one Boustrophedon  algorithm for kissing everyone goodbye – providing they are in a room that is rectangular.

“This paper considers kissing only in rectangular rooms. How quickly can a gathering break up in a less austere environment than a rectangle? What about rectilinear polygons, possibily [sic] with holes (to model those parties where people don’t stand on furniture)?

The boustrophedon algorithm presented here is likely to have better approximation ratios than this paper proves. Could some nontrivial version of the algorithm even be optimal? The complexity of kissing problem remains open for any environment.”

The paper may be found, in full, here.

Also see: Kissing Inclinations, Amsterdam