About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Algorithms
Paper
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.