Aviv Segev, Moshe Ben-Bassat
Faculty of Industrial Engineering and Management
Israel Institute of Technology
Technion, Haifa, 32000, ISRAEL
e-mail: asegev@technion.ac.il
ClickSoftware, 70 Blanchard Road, Burlington
Massachusetts, 01803, USA

Abstract.A main problem when placing systems demarcated by hemispheres is determining coverage. Each system covers an area that can be represented by a hemisphere. The problem is how to cover an arena, a given area, with a minimal number of systems. Determining placement of systems demarcated by hemispheres requires arranging the systems on the plane so that an optimal cover of the plane is obtained. Our approach follows a top-down, stepwise refinement of the problem into simpler subproblems; the combined solution of all the subproblems yields the solution of the original problem. We first show that the original problem can be transformed from three to two-and-a-half dimensions and then decomposed into three subproblems. The first subproblem is finding the tiling possessing the minimal overlap between the hemispheres, the second is determining which hemispheres comprise the cover of a given arena, and the third is finding how the arena should be placed on the tiling.

Received: April 1, 2007

AMS Subject Classification: 51L99, 68Q05

Key Words and Phrases: sorting and searching, graph and tree search strategies, computational geometry, geometric algorithms, edge and feature detection

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 38
Issue: 2