|
7.6 A systematic procedure for district partitioning Consider a
rectangular city district and two stationary facilities located at two
arbitrary points (x1, y1) and (x2, y2) within the district. We wish to
devise procedures that can be used by a computer to partition the
district into two subdistricts so that all the points in the district
are assigned to the facility closest to them. The "inputs" to the
computer will be the coordinates of the locations of the two facilities
and of the corners of the rectangle (the orientation of the rectangle
with respect to the coordinate axes is arbitrary). The "outputs" are the
coordinates of the corners of each subdistrict. a. Devise a procedure for the case in which travel in the district is Euclidean. b. Repeat part (a) for the case of right-angle travel, assuming that directions of travel are parallel to the coordinate axes. (In a special case in which parts of the boundary between the two subdistricts are not uniquely defined, use any arbitrary procedure you wish to specify that boundary.) C. How would your procedure in parts (a) and (b) change if the district's shape was that of an arbitrary polygon with known coordinates for its comer points ? d. Assuming that a procedure has been devised for partitioning a district of arbitrary polygonal shape between two facilities (according to some arbitrary travel metric), how could that procedure be used to partition the district among n randomly located facilities according to the "closest facility" criterion ? Hint: Consider the case when a third facility is suddenly added in a district which has already been partitioned among two facilities. How would the old boundaries be modified? Part (d) of this problem is also discussed in [KEEN 72].
|