WWW.THESIS.XLIBX.INFO FREE ELECTRONIC LIBRARY - Thesis, documentation, books

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 23 | 24 || 26 | 27 |

# «Discrete and Lexicographic Helly Theorems and their Relations to LP-Type Problems Thesis submitted for the degree of “Doctor of Philosophy” by ...»

-- [ Page 25 ] --

The bound in the above lemma must be at least 11 as seen in Example B.2.11 Let B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} be the set of rectangles as described in Figure B.4.

One can verify that the solution on every proper subset of B is lexicographically smaller than on B. (The solution of the 3-lpiercing problem on subsets of 10 rectangles not containing one of {1, 2, 3, 4, 5, 6} is lsmaller than the one on B. The solution on the subset of the 10 rectangles not containing 10 is lsmaller since the middle point can move up to pierce 6 and then the upper point will be lsmaller than before. The solution on the subset of the 10 rectangles not containing 9 is lsmaller since the middle point can move left to become the lsmallest. The solution on the subset of the 10 rectangles not containing 8 is lsmaller since the lower point can move up to pierce 9 and then the middle point will be the lsmallest. The solution on the subset of the 10 rectangles not containing 11 is lsmaller since the lower point can move left to become the lsmallest. The solution on the subset of the 10 rectangles not containing 7 is lsmaller since the middle point can move up to pierce 11 and then the lower point will be the lsmallest.) B.3 Proving Case (iii) Proof: (of Theorem 2.3.4(iii), i.e., h∗ (2, 2) = 6) We ﬁrst show that h∗ (2, 2) ≤ 6. From Theorem 4.1.6 it is suﬃcient to construct for every subset B ⊆ B a solution deﬁning set of cardinality at most 6. Due to Theorem 2.3.

4(i), Lemma B.2.3 and Lemma B.2.5 it remains to study the case where B is not 1-pierceable and no axis-parallel line traverses it. Let bT, bB, bL, bR ∈ B be as deﬁned in Deﬁnition B.2.1 (see Figure B.1). Consider the closed top halfplane H T bounded by the horizontal line, lT, containing the bottom edge of bT, the closed bottom halfplane H B bounded by the horizontal line, lB, containing the top edge of bB, the closed left halfplane H L bounded by the vertical line, lL, containing the right edge of bL and the closed right ∼ halfplane H R bounded by the vertical line, lR, containing the left edge of bR. Let H X denote the closure of the complement of H X, for X = L, R, T, B. As no axis-parallel line traverses B, H L is disjoint from H R, and ∼ H T is disjoint from H B, and thus B0 = ∩X∈{L,R,T,B} H X is a compact rectangle with nonempty interior.

We call B0 the location domain of B (see [SW96]). Let cT L, cBR, cT R and cBL be the upper left, lower right, upper right and lower left corners of B0. [SW96] note that if B is 2-pierceable, then there exists a solution where both piercing points are on the boundary of B0. For such a solution they observe that the 2 piercing points must be either cBL, cT R or cT L, cBR. Using this observation, we formulate in Deﬁnition B.2.1 two types of conﬁgurations for the possible solutions of 2-piercing and 2-lpiercing problems. In Figure B.1 the 4 dashed rectangles determine the location domain B0 whose corners are the big white balls. The bottom-left and top-right small black balls determine the optimal solution of type I. The top-left and bottom-right big

–  –  –

Figure B.4: An instance of the 3-piercing problem where a vertical line traverses all the rectangles.

black balls determine the optimal solution of type II, which is also the optimal solution for the 2-lpiercing problem on the 8 rectangles drawn. Due to the deﬁnitions in this paragraph we obtain Observation B.3.1 Let B be a 2-pierceable ﬁnite set of compact axis-parallel rectangles. If B is not 1pierceable and no axis-parallel line intersects all its rectangles, then every rectangle in B contains at least one of cT L, cBR, cT R and cBL (the corners of its location domain).

By using the observation above we get Observation B.3.2 Let B be as deﬁned in Observation B.3.1.

Every rectangle b in B satisﬁes the following 4 properties:

• If cBL does not pierce b then no point which lies not above and not to the right of cBL pierces b.

• If cT L does not pierce b then no point which lies not below and not to the right of cBL pierces b.

• If cBR does not pierce b then no point which lies not above and not to the left of cBL pierces b.

• If cT R does not pierce b then no point which lies not below and not to the left of cBL pierces b.

We are now ready to build a solution deﬁning set of the 2-lpiercing problem on B as follows. Suppose that there exists a solution for the type I 2-piercing problem on B (i.e., (cBL, cT R ) is a feasible 2-piercing vector of B). We move cBL left and down as much as possible while 2-piercing B as follows. Let b1 = bR (B \ P (cT R )) be a rectangle with the rightmost left edge amongst the rectangles in B which are not pierced by cT R. Let b2 = bT (B \ P (cT R )) be a rectangle with the highest bottom edge amongst the rectangles in B which are not pierced by cT R. From these deﬁnitions it follows that the left edge of b1 intersects the bottom edge of b2. Let cBL be the intersection point of these two edges, and let cT R = cT R. We note that (cBL, cT R ) is the ∗ ∗ ∗ ∗ optimal solution for the type I for the 2-lpiercing problem on B. We now show that

D2I (B) = {bT, bR, b1, b2 }

deﬁnes that optimal solution, i.e., D2I (B) is a solution deﬁning set for the type I 2-lpiercing problem on B.

Intuitively, the type I 2-lpiercing problem on B is decomposed into a 1-lpiercing problem on P (cT R ) (for which {bT, bR } is a solution deﬁning set) and a 1-lpiercing problem on B \ P (cT R ) (for which {b1, b2 } is a solution deﬁning set). The solution deﬁning set for the type I 2-lpiercing problem is simply the union of the deﬁning sets of the two 1-lpiercing problems. It remains to prove that D2I (B) is a solution deﬁning set for B, i.e., the solutions of the type I 2-lpiercing problems on B and on D2I (B) are identical. Due to monotonicity c2I (B) ≥L c2I (D2I (B)). The only possibility that c2I (B) L c2I (D2I (B)) is when at least one of b1, b2 is pierced by the point which pierces both bT, bR. Due to Observation B.3.2 neither b1 nor b2 can be pierced by a point which pierces {bT, bB }, since such a point must lie not below and not to the left of cT R. We note Claim B.3.3 Let B ⊆ B be such that D2I (B) ⊆ B and suppose there exists a solution for the type I 2-lpiercing problem on B. The solutions of the type I 2-lpiercing problems on B and on D2I (B) are equal.

We emphasis that {bT, bR, b1 } deﬁnes the ﬁrst coordinate (out of the 4 coordinates) of the optimal solution of the type I 2-lpiercing problem on B.

Claim B.3.4 Let B ⊆ B be such that {bT, bR, b1 } ⊆ B and suppose there exists a solution for the type I 2-lpiercing problem on B. The ﬁrst coordinate of the solution of the type I 2-lpiercing problem on B is equal to the one on D2I (B).

–  –  –

Claim B.3.5 Let B ⊆ B be such that D2II (B) ⊆ B and suppose there exists a solution of the type II 2-lpiercing problem on B. The solution of this problem on B is equal to the one on D2II (B).

We emphasis that {bT, bR, bB, b3 } deﬁnes the ﬁrst coordinate (out of the 4 coordinates) of the solution of the type II 2-lpiercing problem on B.

Claim B.3.6 Let B ⊆ B be such that {bT, bR, bB, b3 } ⊆ B and suppose there exists a solution of the type II 2-lpiercing problem on B. The ﬁrst coordinate of the type II 2-lpiercing problem on B is equal to the one on D2II (B).

If there doesn’t exist a solution for the type I (type II) 2-piercing problem on B, there exists bI ∈ B (bII ∈ B) that is not pierceable by either cBL or cT R (either cT L or cBR ), respectively.

To summarize, we now formulate D2 (B), the solution deﬁning set for the 2-lpiercing problem on B, according to the cases below.

Case 1 If B is not 2-pierceable then we let D2 (B) = {bT, bB, bL, bR, bI, bII }. Clearly D2 (B) is not 2-pierceable.

Due to monotonicity any B ⊇ D2 (B) is not 2-pierceable, so D2 (B) is a solution deﬁning set.

Case 2 If B is 2-pierceable but is not type II 2-pierceable (so it is type I 2-pierceable), then we let D2 (B) = D2I (B) ∪ {bII }. Due to Claim B.3.3 the solutions of the type I 2-lpiercing problems on B and on D2 (B) are equal. D2 (B) is not type II 2-pierceable since due to Observation B.3.2, bII cannot be pierced by any point which either lies not below and not to the right of cT L, or lies not above and not to the left of cBR.

Case 3 If B is 2-pierceable but is not type I 2-pierceable (so it is type II 2-pierceable), then we let D2 (B) = D2II (B) ∪ {bI }. Due to Claim B.3.5 the solutions of the type II 2-lpiercing problems on B and on D2 (B) are equal. D2 (B) is not type I 2-pierceable since due to Observation B.3.2, bI cannot be pierced by any point which either lies not below and not to the left of cT R, or lies not above and not to the right of cBL.

Case 4 If B is type I 2-pierceable as well as type II 2-pierceable, we compare their values. If c2I (B) L c2II (B) then we let D2 (B) = {bT, bR, bB, b1, b2, b3 }. By Claim B.3.3 the solutions of the type I 2-lpiercing problems on B and on D2 (B) are equal. By Claim B.3.6 the solution of type II 2-lpiercing problem on D2 (B) is inferior to the one of the type I 2-lpiercing problem on the same set. If c2I (B) L c2II (B) then we let D2 (B) = {bT, bR, bB, b1, b3, b4 }. By Claim B.3.5 the solutions of the type II 2-lpiercing problems on B and on D2 (B) are equal. By Claim B.3.4 the solution of the type I 2-lpiercing problem on D2 (B) is inferior to the one of the of the type II 2-lpiercing problem on the same set.

In all cases above the cardinality of D2 (B) is not more than 6 so h∗ (2, 2) ≤ 6. This bound is tight due to Example B.2.2 above.

By Lemma B.2.3 (and the remark below it), Lemma B.2.5 (and the remark below it) and the proof above we conclude with Corollary B.3.7 Let B be a set of rectangles with edges parallel to the coordinate axes. If B is 2-pierceable then there exists a solution deﬁning set for the 2-lpiercing problem on B, D2 (B), such that |D2 (B)| ≤ 6 and bT, bR, bB ∈ D2 (B).

Corollary B.3.8 Let B be a set of rectangles with edges parallel to the coordinate axes such that B is not 2-pierceable. There exists D2 (B), a solution deﬁning set for the 2-lpiercing problem on B such that |D2 (B)| ≤ 6 and bT, bR, bB, bL ∈ D2 (B).

Corollary B.3.9 Let B be a set of rectangles with edges parallel to the coordinate axes. If B is type I 2-pierceable, then there exists a solution deﬁning set for the type I 2-lpiercing problem on B, D2I (B), with |D2I (B)| ≤ 4 and bT, bR ∈ D2I (B).

Corollary B.3.10 Let B be a set of rectangles with edges parallel to the coordinate axes. If B is not type I 2-pierceable, then there exists a solution deﬁning set for the type I 2-lpiercing problem on B, D2I (B), with |D2I (B)| ≤ 5 and bT, bR, bB, bL ∈ D2I (B).

Corollary B.3.11 Let B be a set of rectangles with edges parallel to the coordinate axes. If B is type II 2-pierceable, then there exists a solution deﬁning set for the type II 2-lpiercing problem on B, D2II (B), with |D2II (B)| ≤ 5 and bT, bR, bB ∈ D2II (B).

Corollary B.3.12 Let B be a set of rectangles with edges parallel to the coordinate axes. If B is not type II 2-pierceable, then there exists a solution deﬁning set for the type II 2-lpiercing problem on B, D2II (B), with |D2II (B)| ≤ 5 and bT, bR, bB, bL ∈ D2II (B).

The solution of the 2-lpiercing problem on B as described in Example 2.3.6 (|B| = 6) is lgreater than on any proper subset of B, so h∗ (2, 2) ≥ 6. In Example 2.3.6 B is a set which is traversed by a vertical line. Example B.2.2 illustrates that also when B is not traversed by any axis-parallel, any subset of up to 5-members of B has a lsmaller solution than on B.

B.4 Proving Case (iv) Proof: (of Theorem 2.3.4(iv), i.e., 16 ≤ h∗ (2, 3) ≤ 34) Due to Observation 2.3.12 h∗ (2, 3) ≥ 16. It remains to prove the upper bound. From Theorem 4.1.6 it is suﬃcient to construct for every set B of axisparallel rectangles a solution deﬁning set of cardinality at most 34. Due to Theorem 2.3.4(ii), Lemma B.2.3, Lemma B.2.8 and Theorem 2.1.2 it remains to study the case where B is 3-pierceable but is not 2-pierceable and no axis-parallel line traverses it. Let bT, bB, bL, bR ∈ B be as deﬁned in Deﬁnition B.2.1. Let B0 be the location domain as deﬁned in the proof above. Let cT L, cBR, cT R and cBL be the top left, bottom right, top right and bottom left corners of B0, respectively. Let

–  –  –

such that |B ∗ | ≤ 2 and B∗ ∪ B ∗ is not 2-pierceable (|B∗ ∪ B ∗ | ≤ 6|).

Let (c1, c2, c3 ) ∈ I 6 be a feasible 3-piercing vector for a subset B ⊆ B. We classify the feasible solutions R for the 3-piercing and 3-lpiercing problems on B into 4 types deﬁned as follows (i.e., (c1, c2, c3 ) must be of one of these 4 types).

Type TR: One point (e.g., cT R ) pierces both bT (B ) and bR (B ). The other two points pierce bB (B ) and bL (B ) (either each point pierces exactly one of these rectangles, or one point pierces both and the other point pierces rectangles diﬀerent from bT (B ), bR (B ), bB (B ), bL (B )).

Type BR: One point (e.g., cBR ) pierces both bB (B ) and bR (B ). The other two points pierce bT (B ) and bL (B ) (either each point pierces exactly one of these rectangles, or one point pierces both and the other point pierces rectangles diﬀerent from bT (B ), bR (B ), bB (B ), bL (B )).

Type T L: One point (e.g., cT L ) pierces both bT (B ) and bL (B ). Each one of the other two points pierces exactly one of bB (B ) and bR (B ).

Type BL: One point (e.g., cBL ) pierces both bB (B ) and bL (B ). Each one of the other two points pierces exactly one of bT (B ) and bR (B ).

A ﬁnite set of compact rectangles is 3-pierceable if it is type XX 3-pierceable for XX having value either T R, BR, T L or BL. From now on in this paragraph, we write XX instead of any of T R, BR, T L and BL.

We let c3XX (B ) denote the lexicographically smallest solution of the type XX 3-piercing problem on B, if one exists, and ∞ otherwise. We say that c3XX (B ) is the optimal solution of the type XX 3-lpiercing problem on B. We note that c3 (B ) = lex min{c3T R (B ), c3BR (B ), c3T L (B ), c3BL (B )}. Let D3XX (B ) be a solution deﬁning set for the type XX 3-piercing problem on B (solution of type XX deﬁning set, in short).

Pages:     | 1 |   ...   | 23 | 24 || 26 | 27 |

Similar works:

«Synthesis & Characterization of Sr0.53Ba0.47Nb2O6 based Ferroelectric Composites for Pyroelectric Applications A thesis submitted by S Naresh Kumar in partial fulfillment of the requirements for the award of the degree of Doctor of Philosophy in Physics Department of Physics National Institute of Technology Rourkela, Orissa – 769008 July – 2012 Dedicated to My Beloved Parents Sri S. Anjana Reddy & Smt. S. Venkata Lakshmi Nalluru National Institute of Technology Rourkela India-769008...»

«THE LEVITICAL HEPTATEUCH AND PHINEHAS THE HIGH PRIEST A dissertation by YoungHye Kim Presented to The Faculty of the Graduate Theological Union in partial fulfillment of the requirements for the degree of Doctor of Philosophy Berkeley, California October, 2008 Committee Signatures Robert B. Coote, Coordinator Niek Veldhuis, Member UMI Number: 3335277 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or...»

«QUEEN’S UNIVERSITY BELFAST Gesture Recognition for Musician Computer Interaction by Nicholas Edward Gillian BSc Music Technology, Queen’s University Belfast 2006 MA Sonic Arts, Queen’s University Belfast 2007 A thesis submitted in partial fulﬁllment for the degree of Doctor of Philosophy in the Faculty of Arts, Humanities and Social Sciences School of Music & Sonic Arts March 2011 c Copyright Nicholas Edward Gillian, 2011 All Rights Reserved. i “If we knew what we were doing, it...»

«UNIVERSITÉ DE MONTRÉAL IMPROVING PROGRAM COMPREHENSION AND RECOMMENDATION SYSTEMS USING DEVELOPERS’ CONTEXT ZÉPHYRIN SOH DÉPARTEMENT DE GÉNIE INFORMATIQUE ET GÉNIE LOGICIEL ÉCOLE POLYTECHNIQUE DE MONTRÉAL THÈSE PRÉSENTÉE EN VUE DE L’OBTENTION DU DIPLÔME DE PHILOSOPHIÆ DOCTOR (GÉNIE INFORMATIQUE) DÉCEMBRE 2015 c Zéphyrin Soh, 2015. UNIVERSITÉ DE MONTRÉAL ÉCOLE POLYTECHNIQUE DE MONTRÉAL Cette thèse intitulée: IMPROVING PROGRAM COMPREHENSION AND RECOMMENDATION SYSTEMS...»

«MIXING LIGHT AND MATTER WAVES: PRINCIPLES AND APPLICATIONS By YUPING HUANG A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Physics and Astronomy UMI Number: 3381233 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper...»

«Ph.D. in Electronic and Computer Engineering Dept. of Electrical and Electronic Engineering University of Cagliari Some Proposals for Combining Ensemble Classiﬁers Nima Hatami A dissertation submitted in partial fulﬁllment of the requirements for the degree of Doctor of Philosophy at the University of Cagliari Advisor: Prof. Giuliano Armano Curriculum: ING-INF/05 XXIV Cycle March 2012 Thesis Committee Members • Prof. Giuliano Armano Department of Electrical and Electronic Engineering,...»

«EVALUATION OF THERAPEUTIC STRATEGIES FOR OSTEOARTHRITIS USING CONTRAST BASED CT IMAGING A Dissertation Presented to The Academic Faculty by TanushreeThote In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in Biomedical Engineering Georgia Institute of Technology August 2014 Copyright 2014 by Tanushree Thote EVALUATION OF THERAPEUTIC STRATEGIES FOR OSTEOARTHRITIS USING CONTRAST BASED CT IMAGING Approved by: Dr. Robert E. Guldberg, Advisor Dr. Zigang Ge School of...»

«Computational Software for Building Biochemical Reaction Network Models with Differential Equations Nicholas A. Allen Dissertation submitted to the Faculty of the Virginia Polytechnic Institute and State University in partial fulﬁllment of the requirements for the degree of Doctor of Philosophy in Computer Science and Applications Clifford A. Shaffer, Chairman Lenwood S. Heath Narendran Ramakrishnan John J. Tyson Layne T. Watson November 11, 2005 Blacksburg, Virginia Keywords: biological...»

«DESIRE-SATISFACTION THEORIES OF WELFARE A Dissertation Presented by CHRISTOPHER C. HEATHWOOD Submitted to the Graduate School of the University of Massachusetts Amherst in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY September 2005 Philosophy © Copyright by Christopher C. Heathwood 2005 All Rights Reserved DESIRE-SATISFACTION THEORIES OF WELFARE A Dissertation Presented by CHRISTOPHER C. HEATHWOOD Approved as to content and style by: Fred Feldman, Chair...»

«Exploring Children’s Experiences of NAPLAN: Beyond the Cacophony of Adult Debate Angelique Howell Dip. T. (Primary), (ACU), PGCert (Early Childhood) (ACU), MEd (Leadership) (ACU) A thesis submitted for the degree of Doctor of Philosophy at The University of Queensland in 2015 School of Education Abstract The purpose of this study is to explore how Australia’s National Assessment Program: Literacy and Numeracy (NAPLAN) is experienced by primary school-aged children, with a particular focus...»

«Philosophy of Technical Artefacts Joint Delft Eindhoven Research Programme 2005 – 2010 Programme leaders Peter Kroes and Anthonie Meijers Simon Stevin Series in the Philosophy of Technology Editors: Peter Kroes and Anthonie Meijers Books and Dissertations Volume 1: Marcel Scheele, The proper use of artefacts: A philosophical theory of the social constitution of artefact functions. Research Documents Peter Kroes and Anthonie Meijers (eds.), Philosophy of technical artifacts. Joint Delft...»

«WELLNESS MENU “And now I’ll do what’s best for me.” South Kensington Club is founded upon a belief in the importance of a sustainable, balanced lifestyle when realising ones’ true potential and provides a 360-degree offering that allows its members to embrace this valuable philosophy. Combining a world-class fitness offering with a results-driven, science led treatment menu, a variety of complimentary therapies and a state of the art bathhousewe have the expertise and facilities to...»

<<  HOME   |    CONTACTS
2016 www.thesis.xlibx.info - Thesis, documentation, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.