BEST RELATIVE PLACEMENT
A NEW ABILITY FOR SPATIAL PROCESSING

1) Tehran Univ., Dept. of Surveying Eng. and Geomatics, NCC(Korasan Branch) , Research Dept.
Email: malek@ncc.neda.net.ir

2)University of Applied Sciences Stuttgart, Faculty of Surveying and Geoinformatics
Email: m.hahn.fbv@fht-stuttgart.de

Abstract

In this paper a new spatial function called best relative placement is developed. Two different approaches for solving a BRP problem are discussed which are based on the least-squares method,and interval mathematics. It will be shown that interval mathmatics behaves well even for nonlinear programming tasks. The least-squares and interval methods are examined with a real data.

Keywords : Nonlinear model, spatial analysis, least-squares method.

1. Introduction

The placement is not a new problem. The placement of some subjects with respect to given constraints,frequently take place in urban planning,agriculture, network design in geodesy and so on. In this direction,if relative relations between subjects are given,we call it as relative placement. Consequently we define best relative placement (BRP) as :

Non-precise relative relations,like near,far,etc. are given for n subjects. Therefore,there are n(n+1)/2 independent relations,in addition,some spatial constraints are requested. BRP is a procedure to find the best location of each subject with respect to given region such that all constraints and relations are fulfilled.

The foregoing problem can be considered as a new request of spatial data processing and GIS.

BRP with the mentioned definition cites with

- non precise or fuzzy relations which usually in design level exist,

- most of the target function which have to be optimized are nonlinear. The conventional methods such as Gauss-Newton method require linearisation using approximate values for the unknown parameters. The base of such methods is the fixed point theorem (Malek, 1998) and it is clear that requirements of the theorem are valid if the initial values are sufficiently close to the solutions. The best relative placement problem makes us to use nonlinear objective functions while finding initial valuse is a serious problem .

1.1 Nonlinear objective function in BRP

A nonlinear model of BRP such as distance can be formulated by

Where leR^m is the inputvector, veR^m is the vector of residuals, u e Rⁿ is the vector of unknown parameters, f specifies nonlinear relations from open set U ÚúRⁿ onto an m-dimensional space R^m , P and Q are weight and cofactor matrices,respectively. The minimization problem reads as follows

The objective function (2) gives regard to the inner product < . , .> of the residual vector with itself and leads to detemine f in suchaway to approach l with a minimum distance and then to detemine u (TEUNISSEN,1990).

The optimality condition of the first order,i.e. grad f (u) = 0 leads to the system of nonlinear normal equations and the optimality condition of the second order provides information about the admissibility of the method (LOHSE,1994).

1.2 Interval Mathematics

A real closed interval is defined by

Where x_l is lower bound and x_u is upper bound of [x]. acturatively, an interval can be represented by

where x_m and x_r are mean point and radius, respectively.

A real interval space denoted by RI is defined by

Having inclusion monotony, the mean point theorem states the following (for a proof please refer to KUTTERER 1994)

where f’ is the first derivative interval vector of f. By generalization to Rⁿ an interval vector can be defined by

This means [X] belongs to Rⁿ . In similar way an interval matrix can be formulated as follows :
 
 

Consequently the space of interval matrices is R^m * Rⁿ according to KUTTERER (1994). Arithmetic relations can be defined by

[x]o[y]:= {xoy ½ xI [x], yI [y] " [x],[y] I RI}, oI {+,-,*,/}

if 0 =/,then 0I [y].

More details can be found in (NICKEL, 1980) and (KUTTERER, 1994).

2. Approaches of BRP solution

In the following two approaches will be studied, which are conventional least-squares approach and an interval approach.

2.1 Traditional Least-squares Approach

If it is possible to transform the fuzzy relation into real valued numbers, then the least-squares method can be used. For this purpose fuzzy relations like far and near are fixed ranges, based on experience, designing ideas or any other knowledge. For instance in our case study (sechion 3),the overall size of a certain region is given and far and near can be assumed e.g. by 200 and 5 metres, respectivety. Uncertainty of range values must be takes into account by the weight matrix or in other language by the tensor metric.

The nonlinear target function leads to a nonlinear normal eguation system. As mentioned earlies, the main problem which arises for linearization is finding initial values for the unknown parameters. This nonlinear normal equation system can be solved by applying the conjugate gradient method (CG). Conjugate gradient method converges even with outlying initial valuse (MALEK,1998). It was proved that the CG method always deals with those directions wich quarantees the second order necessary optimality condition (MALEK, 1998).

2.2 Interval Approach

In this approach the fuzziness of input values is described by closed real intervals. All elements of these intervals are assumed to be possible even though they may have different probabilities. Values outside the interval are considered to be impossible. Therefore an input vector is given by:

By means of the left inverse operator of A, i.e.

It has been proved by inclusion monotony of interval function and properties of interval mapping

(KUTTERER, 1994) that

The conjugate gradient method is also applicable here.
 
 

3. Application

A complex with 14 main buildings had to be constructed. There are
 

1,2: Guard building	7-9: Administrative building
3: Food saloon	10,11: Working places
4: Dormitcry	12: Ware house
5: Clinc	13: Repairshopp
6: Directorship building	14: Garages

planing should give regard to the following aspects:

*Working places should be far from dormitorry

* Food salon should be near to dormitory

* Administrative buildings shoud be near to each other

* ….

Acceptable ranges between buildings are provided by the planners (table 1). There are some constraints, too, i.e. in particule the quard buildings and the directorship have fixed location as illustrated in table 2. Hence initial valuse is a serious problem in BRP, thus no newton’s method can yet use. It will through out by using the conjugate gradient method, both on real and interval vectors.
 

14	13	12	11	10	9	8	7	6	5	4	3	2	1
321-621	431-731	369-669	319-719	269-669	249-449	265-449	189-389	.	.	.	53-253	.	.	1
260-460	275-475	143-303	76-176	32-132	66-265	153-253	89-289	.	.	.	143-385	.	.	2
186-586	276-676	186-586	219-519	169-469	117-317	161-361	62-262	.	.	.	.	143-383	53-253	3
256-656	357-757	279-679	266-566	216-616	250-410	259-420	271-331	.	238-398	.	57-137	.	.	4
60-300	157-457	175-475	260-560	275-475	130-310	59-239	117-277	.	.	238-398	198-358	.	.	5
0-300	102-402	73-373	146-446	110-410	67-147	2-82	60-140	.	74-154	247-367	156-316	.	.	6
138-338	215-415	130-330	169-529	124-284	9-109	38-178	.	60-140	117-277	271-33	62-262	89-289	189-389	7
138-338	185-445	130-330	149-349	114-294	40-140	.	38-178	2-82	59-239	259-429	161-361	153-253	265-465	8
112-212	179-359	81-261	109-289	76-236	.	40-140	0-100	67-147	130-310	250-410	117-317	65-265	240-440	9
215-415	207-407	99-199	20-80	.	75-238	114-294	124-284	110-410	275-475	216-616	169-469	32-132	269-669	10
230-430	201-401	91-191	.	20-80	109-289	149-349	169-329	146-446	260-560	266-666	219-519	76-176	319-419	11
122-282	80-240	.	91-191	99-199	81-261	130-330	130-330	73-373	175-475	279-679	186-586	143-303	369-669	12
78-178	.	80-240	201-401	207-407	179-339	185-445	215-415	102-402	157-457	357-757	276-676	285-475	431-731	13
.	78-178	122-262	230-430	215-415	112-212	138-338	138-338	0-300	60-300	256-656	186-586	260-460	321-621	14

You may see the graphical representation of the result as the figure (1).

4. Conclusion

Essence of GIS motivates using fuzzy concepts. Therefore, interval approach came into attention in our concept. It seems that interval mathematics is a powerful tool for best relative placement. Interval mathematicscan be used even in general approach (quadratic programming).

The two previous approaches can be extended to optimization under inequality constraints by quadratic programming (QP). The Kuhn-Tuker theorem serves as the basis of nonlinear QP (PSHENICHNY and DANILIN,1982).

One of interesting advantage of using interval mathematics in this case study, is the manoevre field of designers. In addition, an interval will be become more general by using fuzzy boundaries. In this situation we have

BRPs models as well as many other models which are used in GIS, are nonlinear. The conjugate method is a suitable method, specially when inversion of matrices must be done.

Within this framework interval mathematics and best relative placement have found access to GIS. While using parallel processors and looking for best relative placement functionality, then CG method with interval mathematics work very well. Lastly, interval mathematics, the theory of conjugate method and BRP intiates a new ability for geo-spatial analysis.

REFERNCES

1. Kutterer H. (1994): Intervallmathematische Behandlung endlicher unsch?rfen linearer Ausgleichungsmodelle, Deutsche Geod?tische Komminssion Reihe C, Nr. 423.

2. Lohse P. (1994): Ausgleichungsrechnung in nichtlinearen Modellen, Deutsche Geod?tische Kommission, Reihe C, Nr 429.

3. Malek M.R. (1998): Nonlinear Least-squares Adjustement, K.N. Tossi Univ. of Tech.

4. Nickel K.(1980): interval mathematics 1980. Academic press.

5. Pshenichny B.N., Danilin Y.M. (1982): Numerical Methods in Extremal problem, Mir publishers, second printing.

6. Teunissen P. J. G. (1990): Nonlinear least-squares , Manuscripta Geodaetica, vol. 15,No.?