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

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 24 | 25 || 27 |

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

-- [ Page 26 ] --

In this way c3XX (D3XX (B )) = c3XX (B ). We note that even though the solution of type XX 3-lpiercing problem is unique, its solution deﬁning set is not necessarily unique.

In our proof we decompose the type XX 3-lpiercing problem on B into the 1-lpiercing problem on B, and a 2-lpiercing problem on B 2 of a type to be speciﬁed below, where B = B 1 B 2. (In this way

–  –  –

By cases (i)-(iii) of Theorem 2.3.4 we bound the sizes of a deﬁning set D1 (B 1 ), for the 1-lpiercing problem on B 1 and of a deﬁning set, D2Z (B 2 ), for the type Z 2-lpiercing problem on B 2. We include B∗ in D3XX (B) so that the location domains of D3XX (B) and of B will be identical. We include B ∗ in D3XX (B) in order to make D3XX (B) non 2-pierceable. We note that when XX = T L or XX = BL, the solution of the type XX 3-lpiercing problem on B∗ ∪ B ∗ ∪ D1 (B 1 ) ∪ D2 (B 2 ) may be lsmaller than the one on B. For this reason we will include in D3XX (B) a last subset B3 ⊂ B which will negate such a possibility.

The proof outline is as follows. The main part of the proof is building solution deﬁning sets D3T R (B), D3BR (B), D3T L (B) and D3BL (B) for the 3-lpiercing problems of the 4 types above, with the structure presented in (B.31). Having this at hand, we will use Observation B.4.1 Let D3T R (B), D3BR (B), D3T L (B), D3BL (B) be solution deﬁning sets for the 3-lpiercing problems of the 4 types above. A possible solution deﬁning set for the 3-lpiercing problem on B is

–  –  –

Since we study the case where B is 3-pierceable and not 2-pierceable, the solution of the 3-lpiercing problem on B is of one of the 4 types, say Y Y. Due to the fact that D3Y Y (B) is a deﬁning set for the type Y Y 3-lpiercing

–  –  –

is a type T R solution deﬁning set for the 3-lpiercing problem on B of cardinality at most 11. (See (B.29) and (B.30) for the deﬁnitions of B∗ and B ∗. This shows that B3 = ∅ in (B.31) when XX = T R.). We start by calculating its cardinality. Since D1 (B 1 ) ∩ D2 (B 2 ) = ∅, |D3T R (B) \ (B∗ ∪ B ∗ )| = |D1 (B 1 ) \ (B∗ ∪ B ∗ )| + |D2 (B 2 ) \ (B∗ ∪ B ∗ )|. Since D1 (B 1 ) ⊂ B∗, D1 (B 1 ) \ (B∗ ∪ B ∗ ) = ∅. Since bB ∈ (D2 (B 2 ) ∩ B∗ ), we get that |D2 (B 2 ) \ (B∗ ∪ B ∗ )| ≤ 6 − 1. Hence |D3T R (B) \ (B∗ ∪ B ∗ )| ≤ 5 and |D3T R (B)| ≤ 11. We now show that D3T R (B) is a type T R deﬁning set for B. Due to (B.34) it is enough to show that (D1 (B 1 ), 1); (D2 (B 2 ), 2) is a valid decomposition for the type T R solution of the 3-lpiercing problem on D1 (B 1 )∪D2 (B 2 ). Moving some elements from D2 (B 2 ) to be pierced by the piercing point of D1 (B 1 ) is not possible due to Observation B.3.2 coupled with the fact that all the rectangles in D2 (B 2 ) are not pierced by cT R. On the other hand, when we look for a T R type solution, all the rectangles of D1 (B 1 ) must be pierced by the same piercing point.

Suppose that there exists a feasible solution for the type BR 3-piercing problem on B. (We note that among the solutions of this type the lsmallest point which pierces both bB and bR is either cBR = (xBR, y BR ) or a point (xBR, y) with y y BR.) From the deﬁnition of the rectangles composing B∗, for every valid decomposition of the type BR 3-lpiercing problem on B, ((B 1, 1); (B 2, 2)), the lexicographically greatest point among the 3 piercing points is the piercing point which pierces both bB and bR, i.e., c1 (B 1 ) L c1 (B 2 ) and c1 (B 1 ) L c2 (B 2 ). We now deﬁne such a valid decomposition. Let B 2 = B \ P (cBR ) be the set of all the rectangles of B which are not pierced by cBR. We let c2 (B 2 ) = (c1 (B 2 ), c2 (B 2 )) ∈ I 4 be the solution of the R 2-lpiercing problem on B 2 and D2 (B 2 ) be a solution deﬁning set for this problem. By Corollary B.3.7 we choose D2 (B 2 ) such that |D2 (B 2 )| ≤ 6 and bT (B 2 ) = bT ∈ D2 (B 2 ). Let B 1 = B \ P (c2 (B 2 )) be the set of all the rectangles in B which are pierced by neither c1 (B 2 ) nor c2 (B 2 ). We let c1 (B 1 ) ∈ I 2 be the solution R of the 1-lpiercing problem on B, and D1 (B ) be a solution deﬁning set for this problem. By the remark written after the proof of Lemma B.2.3 (we can use this lemma here since B 1 is 1-pierceable so an horizontal line traverses all its rectangles), we choose D1 (B 1 ) such that |D1 (B 1 )| ≤ 2 and bR (B 1 ) = bR ∈ D1 (B 1 ). We note that by the construction we get that

–  –  –

is a type BR solution deﬁning set of cardinality at most 12. (This shows that B3 = ∅ in (B.31) when XX = BR.) We start with the cardinality calculations. Since bR ∈ (D1 (B 1 ) ∩ B∗ ) and bT ∈ (D2 (B 2 ) ∩ B∗ ) we get |D3BR (D) \ (B∗ ∪ B ∗ )| ≤ (2 − 1) + (6 − 1) = 6, so |D3BR (D)| ≤ 12. We now show that D3BR (B) is a solution deﬁning set for the type BR 3-lpiercing problem on B. Due to (B.35) it is enough to show that (D1 (B 1 ), 1); (D2 (B 2 ), 2) is a valid decomposition for the type BR solution for the 3-lpiercing problem on D1 (B 1 ) ∪ D2 (B 2 ). Moving some elements from D2 (B 2 ) to be pierced by the piercing point of D1 (B 1 ) is not possible due to Observation B.3.2 coupled with the fact that all the rectangles in D2 (B 2 ) are not pierced by cBR. We cannot decrease the solution on D1 (B 1 ) by moving elements from D1 (B 1 ) to be pierced by the piercing points of D2 (B 2 ) (without changing the value of the 2-lpiercing problem to be more than the solution on D2 (B 2 )) as all the rectangles in D1 (B 1 ) are not pierced by c2 (B 2 ).

Suppose that there exists a solution for the type T L 3-piercing problem on B. Hence there exists a valid decomposition (B 1, 1); (B 2, 2I) for the type T L 3-lpiercing problem on B as explained above. To identify such a valid decomposition, we will next successively generate a sequence of decompositions on B, where one of them is the one mentioned above. We note that among the solutions of type T L for the 3-piercing problem on B, the lexicographically smallest point which pierces both bT and bL is either cT L = (xT L, y T L ) or a point (x, y T L ) with x xT L. We observe that we have monotonicity in the sense that P ((x1, y T L )) ⊆ P ((x2, y T L )) ⊆ P (cT L ) for every x1 ≤ x2 ≤ xT L. Let

–  –  –

Let m = |B 1,0 \ {bT, bL }|. We sort the rectangles in B 1,0 \ {bT, bL } = {b1,..., bm } by their left edge such that b1 is a rectangle with the rightmost left edge, and bm is a rectangle with the leftmost left edge. This sorting is not necessarily unique (e.g., when there are several rectangles which have an identical projection of the left edge on the x-axis). For i = 1,..., m let

–  –  –

We let c1 (B 1,i ) ∈ I 2 be the solution of the 1-lpiercing problem on B 1,i. We will later on deﬁne a solution R deﬁning set D1 (B 1,mi ) for the 1-lpiercing problem on B 1,i which satisﬁes

–  –  –

In this way we ensure that all the rectangles in D2I (B 2,j ) must be pierced by two points. Thus we proved that D3T L (B) is a solution deﬁning set for the type T L 3-lpiercing problem on B. |D1 (B 1,j ) \ (B∗ ∪ B ∗ )| ≤ 3 − 2 = 1, |D2I (B 2,j ) \ (B∗ ∪ B ∗ )| ≤ 4 − 1 = 3, and |B3 \ (D1 (B 1,j ) ∪ B∗ ∪ B ∗ )| ≤ (5 + 1) − (2 + 1) = 3 so |D3T L (B) \ (B∗ ∪ B ∗ )| ≤ 1 + 3 + 3 = 7, so |D3T L (B)| ≤ 13.

c1 (B 1,j ) L c1 (B 2,j ): If k = m then we let 2I

–  –  –

Since we are dealing with a type T L solution, these two rectangles must be pierced by the same piercing point. In this case we deﬁne B L = ∅. Otherwise (j = m), because of optimality there exists a rectangle b ∈ {bj+1,..., bk+1 }, such that b is pierced by none of the points in c2I (B 2,j ), and

–  –  –

remaining elements. Otherwise (the solution of the 1-lpiercing problem on D1 (B 1,j ) \ {bj+1 }(= {bT, bL }) is lsmaller than c1 (B 2,j )), due to optimality, B \ P (c1 ({bT, bL })) = B 2,m is not type I 2-pierceable. Hence, 2I by Corollary B.3.10 there exists a subset B L ⊆ B 2,m of at most 5 elements which contains bR (B 2,m ) = bR, bB (B 2,m ) = bB and is not type I 2-pierceable. Thus we can not decrease the solution on D1 (B 1,j ) ∪ D2I (B 2,j ) ∪ B∗ ∪ B ∗ ∪ B L by decomposing it into a 1-lpiercing problem on a proper subset of D1 (B 1,j ) and a 2-lpiercing problem on the remaining elements. We include B L in B3 deﬁned below. By that we guarantee that all the rectangles in D1 (B 1,j ) must be pierced by one point.

We now force all the rectangles in D2I (B 2,j ) to be pierced by two points using the following construction of D2I (B 2,j ). From the monotonicity of the sequence (B 2,i ) we have c2I (B 2,j ) ≥L c2I (B 2,0 ). From optimality we have (c1 (B 2,j ), c2 (B 2,j )) = c2I (B 2,j ) ≤L c2I (B 2,0 ) = (c1 (B 2,0 ), c2 (B 2,0 )) so c2I (B 2,j ) = c2I (B 2,0 ). By 2I 2I 2I 2I monotonicity, since bR, bT, bL, bB (deﬁned as the rectangles with the rightmost left, highest bottom leftmost right and lowest top edge in D2I (B 2,0 ), respectively) are not pierced by cT L, they are not pierced by any c1 (B 1,i ); i = 1,..., m. We let D2I (B 2,j ) = D2I (B 2,0 ) where D2I (B 2,0 ) is deﬁned in (B.36). Since none of the rectangles in B 2,0 is pierced by any c1 (B 1,i );

i = 1,..., m; we conclude that all the rectangles in D2 (B 2,j ) must be pierced by two piercing points. We let

–  –  –

Thus we proved that D3T L (B) is a solution deﬁning set for the type T L 3-lpiercing problem on B. Making the same cardinality calculations as in the previous case we get that |D3T L (B) \ (B∗ ∪ B ∗ )| ≤ 1 + 3 + 3 = 7, so |D3T L (B)| ≤ 13.

From the arguments above D3T L (B) is a deﬁning set of the solution of type T L for the 3-lpiercing problem on B, of cardinality at most 13.

Suppose that there exists a solution for the type BL 3-piercing problem on B. Among the solutions of this type the lexicographically smallest point which pierces both bB and bL is either cBL = (xBL, y BL ) or a point (x, y) with x ≤ xBL and y ≤ y BL. We note that due to Observation B.3.2 we get monotonicity in the sense that P ((x1, y1 )) ⊆ P ((x2, y2 )) ⊆ P (cBL ) for every x1 ≤ x2 ≤ xBL and y1 ≤ y2 ≤ y BL. Let (cx, cy ) = c1, c1, c2 ∈ I 2 be the 3 piercing points in the solution of the type BL 3-lpiercing problem on B, R where c1 pierces both bB and bL. Let c2 = (c1, c2 ). From the existence of a solution of type BL, there exists a valid decomposition (B 1, 1); (B 2, 2II) for the type BL 3-piercing problem on B.

Let B 1 = P (c1 ) be the set of all rectangles in B which c1 pierces (bB, bL ∈ B 1 ). Let B 2 = B \ B 1. Clearly c2 is a 2-piercing vector for B 2 and bT, bR ∈ B 2. Let Br ⊆ B 1 be the set of rectangles with the rightmost left edge which are pierced by c1 (i.e., the projection of their left edge on the x axis is cx ) and not by c2.

Similarly, let Bt ⊆ B 1 be the set of rectangles with the topmost bottom edge which are pierced by c1 (i.e., the projection of their bottom edge on the y axis is cy ) and not by c2. We will next deﬁne {br, bt }, a solution deﬁning set for the 1-lpiercing problem on B 1 which satisﬁes the following properties: The projection of the left edge of br on the x axis is identical to the one of c1 (B 1 ) (so br “deﬁnes” the x coordinate of c1 (B 1 )), and the projection of the bottom edge of bt on the y axis is identical to the one of c1 (B 1 ) (so bt “deﬁnes” the y coordinate of c1 (B 1 )).

We will next deﬁne B3, D1 (B 1 ) and D2I (B 2 ) for (B.31) where XX = BT L, We note that c1 L c2 and that the relative position between c1 and c1 can be one of the following two cases.

c1 L c1 : By Corollary B.3.11 we choose D2II (B 2 ), a solution deﬁning set for the type II 2-lpiercing problem on B 2, such that |D2II (B 2 )| ≤ 5 and bR (B 2 ) = bR, bT (B 2 ) = bT ∈ D2II (B 2 ).

We now deﬁne D1 (B 1 ) and some auxiliary sets BL, BB. If bB ∈ Br (this implies that the solution of the

–  –  –

set for the type II 2-piercing problem on B 2 ∪ Br which satisﬁes the following properties. BL contains 4 rectangles which deﬁne its location domain and a ﬁfth rectangle which negates the existence of a type II solution. Thus |BL | ≤ 5 and bR (B 2 ∪ Br ) = bR, bT (B 2 ∪ Br ) = bT ∈ BL. BL must contain an element from Br which we denote by bl.

Similarly, if bL ∈ Bt (this implies that the solution of the 1-lpiercing problem on B 1 \ Bt ∪ {bB, bL } is not lower than c1 ) we deﬁne bb = bL and BB = ∅. If bL ∈ Bt and bB ∈ Bt we deﬁne bb = bB and BB = ∅.

/1 1 Finally, if bL, bB ∈ Bt then the solution of the 1-lpiercing problem on B 1 \ Bt is lsmaller than c1. Hence, /1 1 because of the optimality, B ∪ Bt is not type II 2-pierceable. Let BB be a solution deﬁning set of the type II 2-piercing problem on B 2 ∪Bt. Due to Corollary B.3.12 we choose BB, a solution deﬁning set for the type II 2-piercing problem on B ∪ Bt r which satisﬁes the following properties. BB contains 4 rectangles which deﬁne its location domain and a ﬁfth rectangle which negates the existence of a type II solution. In this way |BB | ≤ 5 and bR (B 2 ∪ Bt ) = bR, bT (B 2 ∪ Bt ) = bT ∈ BB. BB must contain an element from Bt which we denote by bb. By the deﬁnition of bb, bl ;

–  –  –

and let D3T L (B) = D1 (B 1 ) ∪ D2II (B 2 ) ∪ B3 ∪ B∗ ∪ B ∗.

Thus we proved that D3BL (B) is a deﬁning set for the solution of the type BL 3-lpiercing problem on B.

Clearly |D3BL (B) \ (B∗ ∪ B ∗ )| ≤ (4 − 2) + (5 − 2) + ((5 − 3) + (5 − 3) + 1) = 10, so |D3BL (B)| ≤ 16.

c1 L c1 : Let B 2,0 = B \ P (cBL ) be the set of all the rectangles in B which are not pierced by cBL. Let c2II (B 2,0 ) = (c1 (B 2,0 ), c2 (B 2,0 )) ∈ I 4 be the solution of the type II 2-lpiercing problem on B 2,0. By R 2II 2II Corollary B.3.11 we choose D2II (B 2,0 ) ⊆ B 2,0, a solution deﬁning set for the type II 2-lpiercing problem on B 2,0, such that |D2II (B 2,0 )| ≤ 5 and bR, bT ∈ D2II (B 2,0 ). Since c1 must pierce bB and bL it is not above and not to the right of cBL. Hence, by monotonicity (Observation B.3.2) we get that B 2 ⊇ B 2,0 and c2 ≥L c2II (B 2,0 ). From the optimality of the solution of the 3-lpiercing problem on B, c2 ≤L c2II (B 2,0 ).

Pages:     | 1 |   ...   | 24 | 25 || 27 |

Similar works:

«Seasonal landscape use and conservation of a critically endangered bustard: Bengal florican in Cambodia Charlotte E. Packman Thesis submitted for the degree of Doctor of Philosophy at the University of East Anglia September 2011 © This copy of the thesis has been supplied on condition that anyone who consults it is understood to recognise that its copyright rests with the author and that use of any information derived there from must be in accordance with current UK Copyright Law. In addition,...»

«Synoptic-scale rainfall patterns over southern Africa: Scale-interactions with large-scale modes of variability Neil C. G. Hart Thesis submitted for the degree Doctor of Philosophy Department of Oceanography University of Cape Town South Africa March 2012 For from him and through him and to him are all things; To him be the glory forever! Thesis Abstract i Abstract This dissertation attempts to describe atmospheric dynamics and processes operating over southern Africa at timescales from days to...»

«A Numerical Study of the Sensitivity of Cloudy-Scene Bidirectional Reflectivity Distribution Functions to Variations in Cloud Parameters by Pierre V. Villeneuve Dissertation submitted to the Faculty of the Virginia Polytechnic Institute and State University in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Mechanical Engineering APPROVED J. Robert Mahan, Chairman Curtis H. Stern Elaine P. Scott Douglas J. Nelson James B. Campbell June 28, 1996 Blacksburg,...»

«ABSTRACT Title of Document: DETECTION OF INTERCONNECT FAILURE PRECURSORS USING RF IMPEDANCE ANALYSIS Daeil Kwon, Doctor of Philosophy (Ph.D.), 2010 Directed By: Chair Professor and Director, Michael Pecht, Department of Mechanical Engineering Many failures in electronics result from the loss of electrical continuity of common board-level interconnects such as solder joints. Measurement methods based on DC resistance such as event detectors and data-loggers have long been used by the electronics...»

«PSYCHOSOCIAL STATUS OF CHILDREN WITH AUDITORY PROCESSING DISORDER By NICOLE V. KREISMAN A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA Copyright 2007 by Nicole V. Kreisman For Carl—faithful friend and inspiring mentor—may your legacy live on in part through me and through this work. For my children, Anna Joy and Josiah Peter—for helping to teach me about...»

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

«The Pagan Bible by: Melvin Gorham (Privately published in l962) Contents: Introduction Part I Orientation. Definition of Religion The Emotional Color of Paganism The Barbarian Attitude Our Interest in Religions The Nature of Religions The Existent Religious Cultural Forces The analytical and introspective religions Hinduism, Jainism, and Buddhism Taoism Shinto Western Science The Religions of Expedient Ethics Confucianism Ethical Christian-Democracy The Dogmatic Religions Judaism Christianity...»

«Institut für Kulturwissenschaften Ostund Südasiens Lehrstuhl für Indologie Vorlesungsverzeichnis Wintersemester 2011/12 Lehrstuhl für Indologie Institut für Kulturwissenschaften Ostund Südasiens Am Hubland, Philosophiegebäude 8 U 1-8, 97074 Würzburg Tel. 0931/3185511, e-mail: indologie@mail.uni-wuerzburg.de Homepage: www.indologie.uni-wuerzburg.de/ DozentInnen und MitarbeiterInnen am Lehrstuhl: Prof. Dr. Heidrun Brückner Lehrstuhlinhaberin, z.T. beurlaubt, Raum 8U8, e-mail:...»

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

«SEISMIC COLLAPSE RISK ASSESSMENT OF BUILDINGS: EFFECTS OF INTENSITY MEASURE SELECTION AND COMPUTATIONAL APPROACH A DISSERTATION SUBMITTED TO THE DEPARTMENT OF CIVIL AND ENVIRONMENTAL ENGINEERING AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Laura Eads October 2013 © 2013 by Laura Catherine Eads. All Rights Reserved. Re-distributed by Stanford University under license with the author. This work is...»

«Engineering-Based Problem Solving Strategies In AP Calculus: An Investigation Into High School Student Performance On Related Rate Free-Response Problems by John Thieken A Dissertation Presented in Partial Fulfillment Of the Requirements for the Degree Doctor of Philosophy Approved June 2012 by the Graduate Supervisory Committee: Tirupalavanam Ganesh, Chair Finbarr Sloane James Middleton ARIZONA STATE UNIVERSITY August 2012 ABSTRACT A sample of 127 high school Advanced Placement (AP) Calculus...»

«Appeared in Philosophical Studies 141 (2008), 243-262. Please use the published version for citations and quotations. Persisting Problems for a Quantificational Theory of Complex Demonstratives David Braun University at Buffalo I wish to thank Jeffrey King for his thoughtful and challenging reply to my “Problems for a Quantificational Theory of Complex Demonstratives” (King forthcoming and Braun forthcoming b). I will comment here on some of his responses.1 King (2001, 2008, forthcoming)...»

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