How to play bowling in parallel on the grid

Abstract

Suppose that there are m players each situated at a node of a two-dimensional grid. Every player would like to play bowling by rolling the ball towards one of the boundaries of the grid. Clearly, the paths used by the players should be perpendicular to the boundaries and nonintersecting. We would like to maximize the number of players that are able to play, namely, to find an assignment, of maximum cardinality, of paths to players. Hence, we are interested in solving the following geometrical problem: given a set of m distinguished nodes in a two-dimensional grid, determine a set of non-intersecting straight lines of maximum cardinality such that every line starts at one of the distinguished nodes and connects it to one of the boundaries of the grid. Our main result is an O(m3) algorithm for solving the problem which is the first known polynomial time algorithm for this problem. © 1991.