tailieunhanh - Báo cáo khoa học: Rectilinear spanning trees versus bounding boxes

Tham khảo luận văn - đề án 'báo cáo khoa học: rectilinear spanning trees versus bounding boxes', luận văn - báo cáo, báo cáo khoa học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Rectilinear spanning trees versus bounding boxes D. Rautenbach Forschungsinstitut fur Diskrete Mathematik Universitat Bonn Lennestrasse 2 53113 Bonn Germany rauten@ Submitted Jun 4 2003 Accepted Jul 30 2004 Published Aug 13 2004 Mathematics Subject Classifications 52C99 05C05 Abstract For A. set p cz 1RĨ2 wil II 9 X TĨ. I p r WP nrnvp that p X 1 -I- 3 -L oi a sell J- HA. Vvibn Ăẩ _ n 12 I W u we prove liiai bb p _ yf v n 2 where mst P is the minimum total length of a rectilinear spanning tree for P and bb P is half the perimeter of the bounding box of P. Since the constant -J in the above bound is best-possible this result settles a problem that was mentioned by Brenner and Vygen Networks 38 2001 126-139 . 1 Introduction We consider finite sets of point in the plane R2 where the distance of two points pi xi yi andp2 x2 y2 in R2 is defined as dist pi p2 xi x21 yi y21 . dist p q is the so-called Manhattan or li distance. For a finite set P R2 let mst P be the minimum total length of a rectilinear spanning tree for the set P . mst P is the minimum length of a spanning tree in the complete graph whose vertex set is P and in which the edge pq for p q G P with p q has length dist p q . Let steiner P be the minimum total length of a rectilinear Steiner tree for the set P . steiner P min mst Pz I P R2 and P P . Furthermore let bb P max XliS1 P Xi min x2 y2 eP x2 max x3 y3 eP y3 min x4 y4 eP y . bb P is half the perimeter of the smallest set of the form ai a2 X i 2 that contains P. This unique set is called the bounding box of P. The three parameters mst P steiner P and bb P are examples of so-called net models which are of interest in VLSI design. Clearly mst P steiner P bb P and it is an obvious problem to study upper bounds on mst P or steiner P in terms of bb P . In 1 Brenner and Vygen prove that provided IP I 2 3 r P 2 mst P bb P 9 3 -- Wi OU . 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 N12 1 This result follows from the well-known