TAILIEUCHUNG - 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

• Báo cáo khoa học
• presentation reports
• mathematical knowledge
• reports of mathematics
• mathematical works
• Rectilinear spanning trees
• versus bounding boxes
• Lecture Technical writing and presentation
• Technical writing and presentation
• Writing technical reports/theses
• Structure of a technical report
• Process of thesis writing
• statements and documents scientific reports
• physical reports
• reports agronomy
• biotechnology
• plants Vietnam
• specialized biological
• scientific reports
• presentation of scientific reports
• reports on literature
• philosophy statement
• documents
• studies English language and English language communication and English language commercial
• Information Presentation
• Spoken Dialogue Systems
• Vera Demberg
• model language
• process natural language
• English pronunciation
• presentation report
• agricultural reports
• technical crops
• bio technology
• English reports
• scientific research
• represented
• Wilf on packing distinct
• Tur´n density
• patterns in a permutation
• present report
• the report documents scientific research
• reports in literature
• reports English
• English school
• English learning method
• Even circuits
• prescribed clockwise parity
• industrial building
• agriculture
• Vietnam
• breast cancer
• medicine
• dopamine toxicity
• Structural Biology
• intermediate cells
• biochemistry
• The tumor suppressor p16 INK4a has functions beyond cell cycle control via cyclin dependent kinases
• A coordinated remodeling ofN and O glycosyla tion
• and an increase in the presentation of the endogenous lectin galectin 1 sensing these changes on the surface of p16 INK4a expressing pancreatic carcinoma cells (Capan 1)
• lead to potent pro anoikis signals
• báo cáo khao học
• báo cáo y học
• báo cáo về y học
• công trình y học
• nghiên cứu y học
• báo cáo khoa học
• công trình nghiên cứu về y học
• tài liệu về y học
• cách trình bày báo cáo
• BMC Pediatrics
• Spinal epidural hematoma
• Vascular malformation
• Clinical presentation
• Risk factors
• ourism industry presentations
• Touris Ca Mau
• Ca Mau tourism presentations
• travel guides
• travel reports Mau
• ecotourism