The general Steiner problem in rectangular crisscross space

✍ Scribed by Shou-Tian Ting; Shu-Yu Zhao

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 242 KB
• Volume: 123
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90011-h

✦ Synopsis

The crisscross space is rectangularly structured.

Start from a Cartesian coordinate system with distance D of points defined as D(P1, P,)=Ixz-x,I+Jy2-y,I, where P,=(xr,y,) and P,(x,, yz) are points in the real plane. The general Steiner problem is to find the minimum point P of @(P)=~~=l ciD (P,, p), where p,, i= 1, .._, n, are given points and ci is the weight of Pi. The paper concludes that (1) the 2-dimensional (as well as the n-dimensional) problem can be reduced to a pair of l-dimensional problems: (2) the solution of the l-dimensional problem is determined by the weights only, viz. if there is an integer k (1 <kg n -I) such that cf= 1 ci = xyzk+ 1 ci all points on the interval [xkr xt+ r] are minimum points. In degenerate CdSeS, i.e. when cf= 1 c~=~I_~ ci or when neither of the above kinds of k exist, the solution reduces to a single point. In the 2-dimensional case the solution space is a rectangular region with [x~, xii+ r] and [yj, yj+ ,] as sides. In a degenerate case the solution space reduces to a segment or a point.