Bounds On Some Geometric Transforms
Kamrul Islam · 2005
A flip or edge-replacement can be considered as a transformation by which one edge e of a geometric figure is removed and an edge f (f = e) is inserted such that the resulting figure belongs to the same class as the original figure. This thesis is concerned with transformation of two kinds of geometric objects, namely, planar trees and planar paths, through the application of flips. A technique is presented for transforming a given planar tree into another one for a set of n points in general position in the plane. It is proved that the number of flips required for such a transformation is at most 2n − k − s − 2 (k, s ≥ 1). In the case of planar path transformation we show that any planar path can be transformed into another by at most 2n − 5 flips for a set of n points in convex position in the plane. Besides, experimental results are presented that show transformability of any planar path into another considering n (n ≤ 13) points in general position. Later, we investigate the possibility of using flips, as an enumeration technique to generate the set P(S) of all