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

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 22 | 23 || 25 | 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 24 ] --

We say that c2I (B ) (c2II (B )) is the optimal solution of the type I (type II) 2-lpiercing problem on B, respectively. We note that c2 (B ) = lex min{c2I (B ), c2II (B )}. Let D2I (B ) (D2II (B )) be a solution deﬁning set for the type I (type II) 2-piercing problem on B (solution of type I (type II) deﬁning set, in short), respectively. In this way c2I (D2I (B )) = c2I (B ) and c2II (D2II (B )) = c2II (B )). We note that even though the solution of type I (type II) 2-lpiercing problem is unique, its solution deﬁning set is not necessarily unique, respectively.

To illustrate these deﬁnitions let us look at the following Example B.2.2 Let B = {bT, bB, bR, bL, b1, b2, b3, b4 } be a set of 8 axis-parallel rectangles as drawn in Figure B.1. We ﬁrst note that the “names” of bT, bT, bR and bL are consistent with our deﬁnitions in the sense that bT = bT (B), bB = bB (B), bR (B) = bR and bL (B) = bL. The solution for the type I 2-lpiercing problem on B is the two small black points. A solution of type I deﬁning set for B is D2I (B) = {bT, bR, b1, b2 }.

This solution deﬁning set is the unique inclusion-minimal type I solution deﬁning set for B. The only valid decomposition of D2I (B) is {bT, bR } and {b1, b2 }. The solution for the type II 2-lpiercing problem on B is the two big black points. We observe that the solution of the 2-lpiercing problem on B is realized by this solution. The inclusion-minimal solution of type II deﬁning set for B is D2II (B) = {bT, bR, bB, b3, b4 }.

{bT, b3 } deﬁnes the top left big black point and {bR, b4 } deﬁnes the bottom right big black point. We note that the type II solution on any proper subset of D2II (B) is lsmaller than on B. If the subset does not contain either bT or b3, its top left piercing point is lsmaller. If the subset does not contain either bR or b4 its bottom right piercing point is lsmaller. Finally, the 4-member subset of D2II (B) which does not contain bB yields an lsmaller type II solution since its top left piercing point is the bottom left corner of bT and the remaining 3 rectangles are pierced by a point which lies on the left edge of bR and the bottom edge of b3.

The inclusion-minimal deﬁning set of B is D2 (B) = {bT, bR, bB, b1, b3, b4 }. Any of its proper subsets which does not contain D2II (B), has an lsmaller solution. Its only proper subset that contains D2II (B) is D2II (B) itself and has an lsmaller solution (of type I, where the bottom left point is the bottom left corner of bB ). In this way we conclude that h∗ (2, 2) ≥ 6 (see Theorem 2.3.4).

We ﬁrst prove several lemmas which will serve us in proving cases (iii) and (iv) of Theorem 2.3.4.

–  –  –

Proof: The lemma is correct for p = 1 due to Theorem 2.3.4(i). We now prove the lemma for p 1.

We note that if B ⊆ B is A-p-pierceable, the intervals resulted by intersecting B with the line y = l are p-pierceable. Using the above for every 2p-membered subfamily of B we get by Theorem 2.1.2(ii) that the intervals resulted by intersecting B with the line y = l are p-pierceable, and consequently B is p-pierceable.

By Observation B.0.2 it remains to prove the case where B is not (p − 1)-pierceable. By Theorem 4.1.6 it is suﬃcient to show that for every B ⊆ B there exists a solution deﬁning set of cardinality at most 2p. We give an inductive proof. We ﬁrst deﬁne several special rectangles needed for the formulation of the induction hypothesis. We intersect B with the line y = l and get a family I of intervals which is not (p − 1)pierceable and all of its 2p-membered subfamilies are p-pierceable. By Theorem 2.1.2(ii) I is p-pierceable.

Let (x1,..., xp ) be the solution of the p-lpiercing problem on I. By the proof of Theorem 2.3.4(ii) there exists a subset of p pairwise disjoint intervals of I, Dp (I) = {i1,..., ip }, which is a solution deﬁning set for the p-lpiercing problem on I and where for all j = 1,..., p the leftmost point in ij is xj. For each j = 1,..., p we let Bj ⊂ B be the set of rectangles whose intersection with the line y = l is an interval with a left endpoint equal to the left endpoint of ij. Let bj ∈ Bj be the lexicographically (leftmost right, highest bottom, lowest X top)-most rectangle amongst the rectangles in Bj. Thus the chosen bj is unique. Let Bp = {bj | j = 1,..., p} X (we note that the rectangles in Bp are pairwise disjoint).

To complete the proof of this lemma, we will prove by induction that if B is p-pierceable and is not (p − 1)-pierceable, then there exists a solution deﬁning set, Dp (B), for the p-lpiercing problem on B, of X cardinality at most 2p, which contains Bp.

b2

–  –  –

Figure B.1: An instance of the 2-piercing problem where no axis parallel line traverses all the rectangles.

The induction basis (p = 1) is valid due to Theorem 2.3.4(i) and an appropriate selection of the deﬁning set.

We assume the correctness of the induction hypothesis for p − 1 and prove it for p. We let lR be the vertical line x = x2 and note

–  –  –

Let B L be the set of rectangles of B which are strictly to the left of lR. All b ∈ B L are pierced by (x1, l) and b1 is a rectangle with the rightmost left edge in B L. Let b1 = bT (B L ) be a rectangle with the highest bottom edge among the rectangles in B L (see Figure B.2). Let c1 (B L ) be the solution of the 1-lpiercing problem on B L. We note that D1 (B L ) = {b1, b1 } is a solution deﬁning set for the 1-lpiercing problem on B L so

–  –  –

Remark: We note that bT ∈ Dp (B) (it is also possible to change the above proof by replacing bp with bR so bR ∈ Dp (B)). We note as well that it is easy to choose B such that the solution of the p-lpiercing problem on Dp (B) as deﬁned in the above proof, is lgreater than any solution on any of its proper subsets, so the bound 2p in Lemma B.2.3 is tight.

Since in the lexicographic order the x-coordinate is more important than the y-coordinate, the case where a vertical line intersects all the rectangles is not analogue to the case where a horizonal line intersects all the rectangles.

–  –  –

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

Since bB ∈ D2 (B 2 ), by applying Claim B.2.6 on D2 (B 2 ) we get that the upper piercing point in the solution of the 2-lpiercing on D2 (B 2 ) pierces D1 (B T ) and the lower piercing point pierces D1 (B B ). By (B.9) the upper piercing point in the solution of the 2-lpiercing on B 2 pierces B T and the lower piercing point pierces B B. From monotonicity c2 (D2 (B 2 )) ≤L c2 (B 2 ). If c2 (D2 (B 2 )) L c2 (B 2 ) we get that either c1 (D1 (B T )) L c1 (B T ) or c1 (D1 (B B )) L c1 (B B ), in contradiction to (B.7) and (B.8). Hence

–  –  –

be the set of all the rectangles in B which are pierced by the lexicographically smaller piercing point in the solution of the 2-lpiercing problem on B 2. We note that if c1 (B T ) = c1 (B 2 ) then D1 (B∗ ) = D1 (B T ) is a solution deﬁning set for the 1-lpiercing problem on B∗. We also note that if c1 (B B ) = c1 (B 2 ) then D1 (B∗ ) = D1 (B B ) is a solution deﬁning set for the 1-lpiercing problem on B∗. Hence

–  –  –

B ∗ is 1-pierceable by a point on the line x = l. Let c∗ be the intersection point of the line x = l with the line among {lT, lB } which does not pass through c1 (B 2 ). Since the line x = l intersects all the rectangles in B we get that c∗ intersects all the rectangles in B ∗. Let D1 (B ∗ ) = {bT (B ∗ ), bR (B ∗ )} be a solution deﬁning set for the 1-lpiercing problem on B ∗, so

–  –  –

We note that (c1 (B 2 ), c∗ ) is a feasible solution for the 2-piercing problem on B so (c1 (B), c2 (B)) = c2 (B) ≤L (c1 (B 2 ), c∗ ). B ⊇ B 2, so by monotonicity c2 (B) ≥L c2 (B 2 ) = (c1 (B 2 ), c2 (B 2 )). Hence

–  –  –

By Claim B.2.6, in the solution of the 2-piercing problem on B L, {bT, bR (B T )} must be pierced by the upper piercing point and {bB, bR (B B )} must be pierced by the lower piercing point. Hence, by (B.14) we get Claim B.2.7 Let B ⊆ B be such that B L ⊆ B. The solution of the 2-lpiercing problem on B is of type I if and only if the solution of the 2-lpiercing problem on B L is of type I.

We say that B L deﬁnes the type of the solution of the 2-lpiercing problem on B and that the solutions of the 2-lpiercing problem on B L and on B are of the same type. (We note that if c2 (B) is a solution of type I, then bT, bR ∈ B ∗ so c1 (B) is the lower piercing point. If c2 (B) is a solution of type II, then bT ∈ B∗ and bR ∈ B ∗ so c1 (B) is the upper piercing point).

We now show that D2 (B) = B L ∪ D1 (B∗ ) ∪ D1 (B ∗ ) is a solution deﬁning set for the 2-lpiercing problem on B of cardinality at most 6. We ﬁrst prove that c2 (D2 (B)) = c2 (B).

–  –  –

We recall that either D1 (B∗ ) = D1 (B T ) or D1 (B∗ ) = D1 (B B ) so the rectangles in D1 (B∗ ) are either both not below lT or both not above lB. By applying Claim B.2.6 on D2 (B), the rectangles in D1 (B∗ ) are covered by the same piercing point. By Claim B.2.7 the solutions of the 2-lpiercing problem on B and on D2 (B) are of the same type. Hence c1 (D2 (B)) pierces D1 (B∗ ) (and possibly more rectangles from D2 (B)). By monotonicity c1 (D2 (B)) ≥L c1 (D1 (B∗ )) so from (B.16) we get c1 (D2 (B)) = c1 (D1 (B∗ )). By the former equation and the deﬁnition of B ∗, the rectangles in D1 (B ∗ ) are not pierced by c1 (D2 (B)). Hence c2 (D2 (B)) ≥L c1 (D1 (B ∗ )), so from (B.16) we get c2 (D2 (B)) = c1 (D1 (B∗ )). Thus By (B.12), (B.13) and (B.15) we get that c2 (D2 (B)) = c2 (B).

It remains to prove that |D2 (B)| ≤ 6. We ﬁrst note that bT ∈ B L ∩ (D1 (B∗ ) ∪ D1 (B ∗ )) so |D2 (B)| ≤ (4+2+2)−1 = 7. In order to give a smaller bound we need to look at two diﬀerent cases. If c1 (B T ) = c1 (B 2 ) then D1 (B∗ ) = D1 (B T ) ⊂ B L, so |D2 (B)| ≤ 6. Otherwise (c1 (B B ) = c1 (B 2 )) D1 (B∗ ) = D1 (B B ) so bR (B B ) ∈ D1 (B∗ ) ∩ B L and thus |D2 (B)| ≤ 6.

Remark: We note that bT, bB, bR ∈ D2 (B). We note as well that

–  –  –

(if {bT, bR } is not 1-pierceable then we deﬁne P (c1 ({bT, bR })) = B) is a solution deﬁning set for the type I 2-lpiercing problem on B. Hence bT, bR ∈ D2I (B) and |D2I (B)| ≤ 4. We also note that

–  –  –

is a solution deﬁning set for the type II 2-lpiercing problem on B. Hence bT, bR, bB ∈ D2II (B) and |D2II (B)| ≤ 5 (we will use the representations of D2I (B), D2II (B) in the proof of Theorem 2.3.4 (iv)).

In Figure B.3 we have B = {1, 2, 3, 4, 5, 6}, B T = {3, 4}, B B = {5, 6} and B T B = {1, 2}. bT = 3, b (B B ) = 5, bB = 5, bR = 2, bR (B T ) = 4 and bR (B B ) = 6. The solution of the 2-lpiercing problem on B is T the two small black points. Thus B∗ = {3, 4}, B ∗ = {1, 2, 5, 6} and c∗ is the big white point. Example 2.3.6 demonstrates that the bound 6 in the above lemma is tight.

Lemma B.2.8 Let B be a ﬁnite family of at least 13 compact rectangles in the plane, all traversed by a vertical line x = l and let A ∈ I 3,2. If every 13-membered subfamily of B is A-3-pierceable then B is R A-3-pierceable.

Proof: If B is 2-pierceable then by Lemma B.2.5 above we are done. We assume from now on that B is not 2-pierceable. From Theorem 4.1.6 it is suﬃcient to prove that for every B ⊆ B there exists a solution deﬁning set for the 3-lpiercing problem on B of cardinality at most 13. Let I be the set of intervals resulted by intersecting B with the line x = l. If I is not 3-pierceable then by Theorem 2.1.2(ii) there are 4 intervals which are not 3-pierceable and hence there is a D3 (B) ⊆ B of cardinality 4 that is not 3-pierceable. Else (I is 3-pierceable) B is 3-pierceable.

–  –  –

must be pierced by the lower piercing point. Hence, by (B.25) we get Claim B.2.10 Let B ⊆ B be such that B L ⊆ B. The lexicographically smallest piercing point in the solution of the 3-lpiercing problem on B is the upper (middle, lower) piercing point if and only if the lexicographically smallest piercing point in the solution of the 3-lpiercing problem on B is the upper (middle, lower) piercing point, respectively.

We say that B L deﬁnes the type of the solution of the 3-lpiercing problem on B and that the solutions of the 3-lpiercing problem on B L and on B are of the same type.

We now show that D3 (B) = B L ∪ D1 (B∗ ) ∪ D2 (B ∗ ) is a solution deﬁning set for the 3-lpiercing problem on B of cardinality at most 13.

We ﬁrst prove that c3 (D3 (B)) = c3 (B). By monotonicity c3 (D3 (B)) ≤L c3 (B). From (B.23), (B.24) and (B.26) we get that c3 (B) = (c1 (D1 (B∗ )), c2 (D2 (B ∗ ))), so

c3 (D3 (B)) ≤L (c1 (D1 (B∗ )), c2 (D2 (B ∗ ))). (B.28)

We recall that D1 (B∗ ) equals either D1 (B T ), D1 (B M ), or D1 (B B ), so the rectangles in D1 (B∗ ) are either both not below lT, or both below lT and above lB, or both not above lB. By applying Claim B.2.9 on D3 (B), the rectangles in D1 (B∗ ) are covered by the same piercing point. Using Claim B.2.10 with B = D3 (B), we get that the solutions of the 3-lpiercing problem on B and on D3 (B) are of the same type. Hence c1 (D3 (B)) pierces D1 (B∗ ) (and possibly more rectangles from D3 (B)). By monotonicity c1 (D3 (B)) ≥L c1 (D1 (B∗ )) so from (B.28) we get c1 (D3 (B)) = c1 (D1 (B∗ )). By the former equation and the deﬁnition of B ∗ the rectangles in D2 (B ∗ ) are not pierced by c1 (D3 (B)). Hence by monotonicity (c2 (D3 (B)), c3 (D3 (B))) ≥L c2 (D2 (B ∗ )), so from (B.28) we get (c2 (D3 (B)), c3 (D3 (B))) = c2 (D2 (B∗ )). Thus by (B.23), (B.24) and (B.26) we get that c3 (D3 (B)) = c3 (B).

It remains to prove that |D3 (B)| ≤ 13. We choose D2 (B ∗ ) as constructed in the proof of Lemma B.2.5, so |D2 (B ∗ )| ≤ 6. By (B.20) and (B.26) there are 3 cases to handle.

–  –  –

and B T B = {1, 2}. The optimal solution on B is indicated by the 3 black points. Thus B∗ = {5, 6}, B ∗ = {1, 2, 3, 4, 7, 8, 9, 10, 11} and c∗ is the 2 white points.

Pages:     | 1 |   ...   | 22 | 23 || 25 | 26 |   ...   | 27 |

Similar works:

«EFFICIENT USER-LEVEL EVENT NOTIFICATION by Michael Allen Parker A dissertation submitted to the faculty of The University of Utah in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science School of Computing The University of Utah August 2013 Copyright © Michael Allen Parker 2013 All Rights Reserved The U n i v e r s i t y of Utah G r a d u a t e School STATEMENT OF DISSERTATION APPROVAL The dissertation of Michael Allen Parker has been approved by...»

«The packaging of 7SL RNA by 1 by Sarah Elizabeth Keene A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Microbiology and Immunology) in the University of Michigan 2012 Dissertation committee: Associate Professor Alice Telesnitsky, Chair Professor Kathy Spindler Professor Nils G. Walter Associate Professor David J. Miller Assistant Professor Akira Ono © Sarah Elizabeth Keene All rights reserved. Acknowledgments I am grateful to my...»

«An Ethnography o f Alterity: Margins, Markets, Morality. David Evans BScEcon, MSc This thesis is submitted in candidature for the degree of Doctor of Philosophy School of Social Sciences Cardiff University UMI Number: U584093 All rights reserved INFORMATION TO ALL USERS The quality of this reproduction is dependent upon the quality of the copy submitted. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if material...»

«The Conventionality of Epistemic Norms Dissertation Proposal Tucker Lentz Department of Logic and Philosophy of Science University of California, Irvine Fall 2010 Table of Contents: Project Description Sample Chapter: Conventions and the Role of Salience Extended Research Bibliography Reading List Project Description: I propose to write a dissertation in the area of evolutionary epistemology that seeks to determine whether or not, or to what extent, our epistemic norms are conventional. I have...»

«ABSTRACT Title of Dissertation: WHAT DO CHILDREN HAVE IN THEIR HEADS? FUNCTIONAL HEADS AND PARAMETER SETTING IN CHILD LANGUAGE Graciela Mariel Tesan, Doctor of Philosophy, 2005 Dissertation directed by Professor Rosalind Thornton Department of Linguistics The aim of the present study is to revisit the old debate between rationalists and empiricists in relation to language development with new longitudinal data in hand. I show that when it comes to the development of a specific piece of...»

«NANOMATERIALS FOR ENERGY STORAGE Feng Jiao A Thesis Submitted for the Degree of PhD at the University of St. Andrews Full metadata for this item is available in the St Andrews Digital Research Repository at: https://research-repository.st-andrews.ac.uk/ Please use this identifier to cite or link to this item: http://hdl.handle.net/10023/487 This item is protected by original copyright This item is licensed under a Creative Commons License Nanomaterials for Energy Storage A Thesis presented for...»

«This dissertation is submitted in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY (Ph.D.) at the IT University of Copenhagen. Candidate: Lisbeth Klastrup Supervisor: Anker Helms Jørgensen Acknowledgements I am greatly indebted to a great number of people for ideas, suggestions, and feedback. Thanks to all of you – also to those of you I only know from the world of blogging but who provided me with numerous interesting links. Thank you to my students in the...»

«Two Sides of Self-Enhancement in Consumer Word-of-Mouth by Grant M. Packard A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Business Administration) in The University of Michigan Doctoral Committee: Associate Professor David B. Wooten, Chair Professor Richard P. Bagozzi Professor Gerald F. Davis Associate Professor Stephen M. Garcia Associate Professor Andrew D. Gershoff, University of Texas © Grant M. Packard RebeccaThank you for...»

«University of Iowa Iowa Research Online Theses and Dissertations Here and gone: competing discourses in the communication of families with a transgender member Kristen Michelle Norwood University of Iowa Copyright 2010 Kristen Michelle Norwood This dissertation is available at Iowa Research Online: http://ir.uiowa.edu/etd/564 Recommended Citation Norwood, Kristen Michelle. Here and gone: competing discourses in the communication of families with a transgender member. PhD (Doctor of Philosophy)...»

«A PHENOMENOLOGICAL INVESTIGATION INTO THE EFFECTS OF TRADITIONAL BELIEFS AND PRACTICES ON WOMEN AND HIV & AIDS, WITH SPECIAL REFERENCE TO CHIPINGE DISTRICT, ZIMBABWE. BY TAPIWA PRAISE MAPURANGA A DISSERTATION SUBMITTED IN FULFILLMENT OF THE REQUIREMENT FOR THE DEGREE OF DOCTOR OF PHILOSOPHY DEPARTMENT OF RELIGIOUS STUDIES CLASSICS AND PHILOSOPHY OF THE UNIVERSITY OF ZIMBABWE JUNE 2010 SUPERVISOR: PROFESSOR E. CHITANDO i Dedication I dedicate this thesis to my late parents Judith Chenesai &...»

«Copyright by Stephanie Jennings Hanor The Dissertation Committee for Stephanie Jennings Hanor certifies that this is the approved version of the following dissertation: Jean Tinguely: Useless Machines and Mechanical Performers, 1955–1970.Committee: Linda D. Henderson, Supervisor Michael Charlesworth Neil Nehring Ann Reynolds Richard Shiff Jean Tinguely: Useless Machines and Mechanical Performers, 1955–1970. by Stephanie Jennings Hanor, M.A., B.A. Dissertation Presented to the Faculty of the...»

«DIPLOMARBEIT Titel der Diplomarbeit „Kollektive Filmprojekte im Web 2.0 Filmproduktion im Kontext von New Media“ Verfasserin Stefanie Amlacher angestrebter akademischer Grad Magistra der Philosophie (Mag.phil.) Wien, 2012 Studienkennzahl lt. Studienblatt: A 317 Studienrichtung lt. Studienblatt: Theater-, Filmund Medienwissenschaft Betreuer: Univ.-Prof. Mag. Dr. habil. Ramón Reichert Für meine Schwester. Für die Betreuung der Diplomarbeit und die konsequente Unterstützung möchte ich...»

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