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

<< HOME
CONTACTS

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

The projection of P+ on the x-axis results an interval [slmin, slmax ] of non-negative slopes with which there exists a line transversal for D. Similarly, the projection of P− on the x-axis results an interval [slmin, slmax ] of non-positive slopes with which there exists a line transversal for D. We call [slmin, slmax ] ∪ [slmin, slmax ] the slope range corresponding to D. The 2 rectangles dl (P− ), dl (P− ) determine slmin, the minimal non-positive slope of a line transversal for D. Similarly, dr (P+ ), dr (P+ ) determine slmax, the maximal non-negative slope of a line transversal for D. For example, let D1 be the set consisting of the 4 pairwise disjoint translates of a square as drawn in Figure A.3. Rectangles 1 and 2 determine the maximal non-negative slope of a line transversal, and rectangles 3 and 4 determine the minimal non-positive slope of a line transversal. In this example the range of non-positive slopes of line transversals for D1 is [slmin, slmax ] = [−0.2, 0] and the range of non-negative slopes is [slmin, slmax ] = [0, 0.2]. Any subset of D1 containing only 3 rectangles has a slope range strictly containing the slope range corresponding to D1. We note moving the squares in Figure A.3 towards the origin, may cause their slope range to strictly contain the slope range corresponding to D1. Let D2 be the set consisting of the 4 squares in a ﬁgure such as Figure A.3 rotated by Π radians relatively to the origin.

The slope range corresponding to D2 is [slmin, slmax ] = [−∞, −5] and [slmin, slmax ] = [5, ∞]. Any subset of D2 containing only 3 rectangles has a slope range strictly containing the slope range corresponding to D2.

Again, we note that moving the squares towards the origin may result a slope range strictly containing the original one. We note that D1 ∪D2 does not admit a line transversal, since the intersection of the slope ranges corresponding to D1 and D2 is empty. We now show that it is not possible to move the squares in D1 ∪ D2 towards the origin, while keeping the squares pairwise disjoint, such that the slope range corresponding to the 8 translated squares is not empty and is diﬀerent from the slope range corresponding to any subset of 7 squares. We will show that the above holds even if we take translates of a rectangle instead of a square.

Let y denote the height of the rectangle O and let x denote its width. In Figure A.4(a) the 4 rectangles are moved as much as possible towards the origin. Let D1 be the set consisting of these 4 rectangles, and let y α be the maximal angle of a line transversal for D1. We get that α = arctan 2x. Similarly, in Figure A.4(b) the 4 rectangles are moved as much as possible towards the origin. Let D2 be the set consisting of these 4 rectangles, and let β be the angle between the y-axis and the line transversal for D2 with the minimal positive x slope. We get that β = arctan 2y. (We note that a rectangle in D1 may have a non-empty intersection with a rectangle in D2 ). In order to get that D1 ∪ D2 admits a line transversal, we must have α + β ≥ Π. To 2 conclude our proof it is therefore suﬃcient to show that α + β Π. 2

–  –  –

We get f (1) 0 so f (z) attains its minimum in z = 1 (f (1) = 2 arctan 2 Π ). We note that for any other positive ﬁnite value for z we still get α + β = f (z) Π as needed.

We now determine a solution deﬁning set for D. If P+ ∪ P− does not intersect any of the vertical lines in D(S ) we set D = {dl (P− ), dl (P− ), dr (P− ), dr (P− ), dl (P+ ), dl (P+ ), dr (P+ ), dr (P+ )}.

Otherwise, let x = a the vertical line in D(S ) with the minimal a which P+ ∪ P− intersects. We let d∗ ∈ D be a rectangle such that the lowest (w.r.t. the y-axis) intersection point (a, y ), of the polygon D(d∗ ) with the line x = a, has the highest y. If P− intersects the line x = a we set D = {dl (P− ), dl (P− ), d∗ }.

Otherwise P+ intersects the line x = a and we set D = {dl (P− ), dl (P− ), dr (P− ), dr (P− ), dl (P+ ), dl (P+ ), d∗ }.

If D does not admit a line transversal, then due to Theorem 2.1.8(v) there are at most 5 translates in D which do not admit a line transversal. We set D to consist of these rectangles.

In all cases, (D, S ) is a solution deﬁning set for (D, S ) with cardinality at most 7, as needed.

The following example shows that the Helly number cannot be reduced to 6

Example A.2.6 Let D = {a, b, c, d, e, f, g} consists of the 4-units length open squares such that a is centered at (2,2); b is centered at (−2 4, 0); c is centered at (−2 9, 4); d is centered at ( 4, 8), e is centered at (−1 2, −4);

f is centered at (−1, 12); and g is centered at ( 7, −8). Let a = b = 100.

max = 8, a and c determine slmin = −18, d and e determine We observe that a and b determine sl min = 4 17, and f and g determine slmax = −7. Hence the corresponding slope range is [−18, −7] ∪ [4 17, 8].

sl Let S = {−18 −, −7 +, 4 17 −, 8 + } (all of these slopes are smaller than a ). Since D is ﬁnite it is possible to choose 0 small enough such that D does not have a line transversal with direction in S but any of its proper subsets does.

(We note that there exists δ 0 small enough such that we can modify this example to closed squares of length 4 − δ, so the corresponding slope range will not change signiﬁcantly, and consequently the set of slope directions will be similar to S) We note that Theorem 2.4.6(iii),(iv) implies Theorem 2.2.10(iii),(iv) in the following way. Due to Observation 2.4.8, the Helly number in Theorem 2.2.10(iii),(iv) is bounded from above by 7, the Helly number in Theorem 2.4.

6(iii),(iv). Due to Example A.2.6, it is at least 7, so it is 7.

–  –  –

Figure A.4: 8 rectangles and their corresponding line transversals slope ranges.

A.3 Discrete and lex variants of Theorem 2.1.6 (Theorems 2.2.9, 2.3.9 and 2.4.5) We start by proving a lexicographic version of Theorem 2.1.6 Proof: (of Theorem 2.3.9) We consider the corresponding dual problem. Due to Observation A.2.4, each rectangle d ∈ D in the primal is transformed into a polygon D(d) such that its intersection with the x non-negative halfplane is a convex polygon p(d). Due to Observation A.2.2, D admits a line transversal y = ax + b with a non-negative slope a and (a, b) ≤L (a, b ) if and only if the convex polygon ∩d∈D p(d) contains a point which is not lexicographically greater than (a, b ). We conclude the proof by applying the lexicographic version of Helly’s theorem (Theorem 2.3.2) on the convex polygons p(d), ∀d ∈ D.

We now prove a lex-discrete version of Theorem 2.1.6 by using Theorem 4.2.5 Proof: (of Theorem 2.4.5) We will use the duality transformation D from Deﬁnition A.2.1. Let ω : 2D ×2S →I 2 ∪{∞} be a function such that for every (D, S ) ∈ 2D ×2S, ω(D, S ) is the lexicographically R smallest point in ∩d ∈D D(d ) with x-coordinate in S, if such intersection is not empty, and ∞ otherwise.

The deﬁnition of ω together with Observation A.2.2 implies that for every a, b ∈ I and (D, S ) ∈ 2D × 2S, R the rectangles in D are met by a common line y = ax + b with (a, b) ≤L (a, b ) and a ∈ S if and only if ω(D, S ) ≤L (a, b ). Moreover, since set intersection is monotone (i.e., A ∩ B ⊆ A, B), (D, S, ω) is a discrete abstract problem (see Deﬁnition 3.3.2), which meets the Monotonicity of Demand Condition. Hence, due to Theorem 4.2.

5, it is suﬃcient to show that for every (D, S ) ∈ 2D × 2S, there exists a solution deﬁning set (D, S ) with |D | ≤ 4. orem).

If D does not admit a line transversal, by Theorem 2.1.6 there are 3 rectangles in D which do not admit a common line transversal. We let D be the set consisting of these rectangles.

Otherwise we let P+, dl (P+ ), dl (P+ ), dr (P+ ) and dr (P+ ) be as deﬁned in the proof of Theorem 2.4.6(iii),(iv).

If P+ does not intersect any of the vertical lines in D(S ) we set D = {dl (P− ), dl (P− ), dr (P− ), dr (P− )}.

If P+ does intersect D(S ), we let x = a be the vertical line in D(S) with the minimal a which P− intersects. We let d∗ ∈ D be such that the lowest (w.r.t. the y-axis) intersection point (a, y ), of the polygon D(d∗ ) with the line x = a, has the highest y. We set D = {dl (P− ), dl (P− ), d∗ }.

In all cases, (D, S ) is a solution deﬁning set for (D, S ) with cardinality at most 4, as needed.

The Helly number cannot be reduced to 3 due to Example A.2.5 (with a = b = 2).

Corollary A.3.1 Let D be a family of axis-parallel rectangles in the plane and for every d ∈ D, let D(d) be the set of line transversals which d admits in the dual (see Deﬁnition A.2.1). Let P (D) = ∩d∈D D(d) be the set of line transversals which D admits. The intersection of P (D) with either the x non-negative or x non-positive halfplanes is a convex polygon. The slopes of line transversals with non-negative (non-positive) slopes for D generate an interval [slmin, slmax] ([slmin, slmax ]) resulted by the projection of P (D) on the nonnegative (non-positive) part of the x-axis, respectively. Each of the 4 endpoints of these two intervals is determined by two rectangles.

We note that Theorem 2.4.5 implies Theorem 2.2.9 in the following way. Due to Observation 2.4.8, the Helly number in Theorem 2.2.9 is bounded from above by 4. Due to Example A.2.5, it is at least 4, so it is 4.

Appendix B Proving Theorem 2.3.4 In this chapter we prove Theorem 2.3.4, that is

–  –  –

We note that so far we have shown in Section 2.3 that h∗ (2, 2) h(2, 2) and that h∗ (3, 1) h(3, 1) = 2.

Before proving Theorem 2.3.4, we comment on the relation between non-lexicographic and lexicographic p-pierceability.

–  –  –

Proof: We ﬁrst note that for every (p − 1)-pierceable B, there is a lexicographically large enough point M ∈ I d such that B is Ap−1 -(p − 1)-pierceable for Ap−1 = (M,..., M ). Moreover R

–  –  –

B.1 Proving Cases (i), (ii) and (v) Proof: (of Theorem 2.3.4 cases (i),(ii) and (v)) Let B be a ﬁnite set of axis-parallel rectangles in I d and let (B, ωp ) be an abstract problem over the totally R ordered set I 2p ∪ {∞} where for every B ⊆ B and natural number p, ωp (B ) is the lexicographically R smallest p-piercing vector which is feasible for B (if B is not p-pierceable, we set ωp (B ) = ∞). Since adding a rectangle b to B cannot lexicographically decrease the lexicographically smallest feasible p-piercing vector, i.e., ωp (B ∪ {b}) ≥L ωp (B), we get that (B, ωp ) is an abstract problem which meets the Monotonicity Condition. From Theorem 4.1.6 it is suﬃcient to ﬁnd for every B ⊆ B a solution deﬁning set for B with cardinality which is bounded by the Helly number we want to prove. Let Aopt be the solution of the lexicographic p-piercing optimization problem on B.

Case (i) (h∗ (d, 1) = max(2, d)) We ﬁrst show that h∗ (d, 1) ≥ max(2, d). By Observation 2.3.12 and Theorem 2.1.2(i) h∗ (d, 1) ≥ h(d, 1) = 2. If B is 1-pierceable, for every i = 1,..., d we project B onto the i’th coordinate and thus get a one dimensional 1-piercing problem. Let bi ∈ B be a box whose projection on the i’th coordinate is an interval [li, ri ] with the greatest li. Since B intersects, li is inside the projection of B on the i’th coordinate. Let B = {b1,..., bd }. We observe that Aopt = (l1,..., ld ). It is possible to choose a set B such that B and B are Aopt -1-pierceable and there exists a suﬃciently small 0 such that neither B nor B are (l1,..., ld − )-1-pierceable but every proper subset of B is (l1,..., ld − )-1-pierceable. Hence h∗ (d, 1) ≥ max(2, d).

We now show that h∗ (d, 1) ≤ max(2, d). If there exist 2 boxes in B which are disjoint then B is not 1-pierceable. If every 2 boxes of B intersect then by Theorem 2.1.2(i) B intersects, and the lexicographically smallest intersection vector is determined by B deﬁned above. B is a solution deﬁning set for B of cardinality at most d. Hence h∗ (d, 1) ≤ max(2, d).

Case (ii) (h∗ (1, p) = p + 1) From Theorem 2.1.2(ii) and Observation 2.3.12 it remains to prove that h∗ (1, p) ≤ p + 1. If there exist p + 1 intervals in B which are pairwise disjoint then B is not p-pierceable and these p + 1 intervals serve as a solution deﬁning set for B. If every p + 1 intervals of B are p-pierceable then by Theorem 2.1.2(ii) B is p-pierceable. We can suppose it is not (p − 1)-pierceable. Let bp ∈ B be an interval [lp, rp ] with the greatest lp (if there are several such intervals, we choose the one with the minimal rp ). We look at the set of intervals which are not pierced by lp and deﬁne bp−1,..., b1 and lp−1,..., l1 recursively. Let B = {b1,..., bp }. B is a solution deﬁning set for B of cardinality at most p. (We note that if there are several intervals with greatest lp, not choosing the one with the minimal rp may cause B not to be a solution deﬁning set for B.) Thus, we conclude that h∗ (1, p) ≤ p + 1.

Case (v) (h∗ (d, p) = ∞ for d ≥ 2, p ≥ 3 and (d, p) = (2, 3)) It follows directly from Theorem 2.1.2(v) and Observation 2.3.12.

B.2 Some useful deﬁnitions and lemmas In order to prove cases (iii) and (iv) we need to give several deﬁnitions.

Deﬁnition B.2.1 Let B be a ﬁnite family of axis-parallel compact rectangles in the plane.

–  –  –

• Suppose B is 2-pierceable and let B ⊆ B. Let (c1, c2 ) ∈ I 4 be a feasible 2-piercing vector of B. We R say that (c1, c2 ) is a solution of type I and that B is type I 2-pierceable, if one of c1, c2 pierces both bT (B ) and bR (B ). Otherwise we say that (c1, c2 ) is a solution of type II and that B is type II 2pierceable. A ﬁnite set of compact rectangles is 2-pierceable if either it is type I 2-pierceable or type II 2-pierceable or both. We note that a ﬁnite set of compact rectangles may be 2-pierceable and not type I (type II) 2-pierceable, respectively. We let c2I (B ) (c2II (B )) denote the lexicographically smallest solution of the type I (type II) 2-piercing problem on B, if one exists, and ∞ otherwise, respectively.

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

Similar works:

«Transition Regime Collisions in Aerosols A DISSERTATION SUBMITTED TO THE FACULTY OF UNIVERSITY OF MINNESOTA BY Ranganathan Gopalakrishnan IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Professor Christopher J. Hogan Jr. Professor Peter H. McMurry August 2013 © Ranganathan Gopalakrishnan 2013 Acknowledgements None of this would have been possible sans the support and guidance of my advisers Professors Chris Hogan and Peter McMurry. They have helped this kid...»

«Essays on Space-Time Interaction Tests by Nicholas Malizia A Dissertation Presented in Partial Fulﬁllment of the Requirements for the Degree Doctor of Philosophy Approved March 2013 by the Graduate Supervisory Committee: Luc Anselin, Chair Alan Murray Sergio Rey ARIZONA STATE UNIVERSITY May 2013 ABSTRACT Researchers across a variety of ﬁelds are often interested in determining if data are of a random nature or if they exhibit patterning which may be the result of some alternative and...»

«Copyright by Nigel Charles Andrew Pitman A LARGE-SCALE INVENTORY OF TWO AMAZONIAN TREE COMMUNITIES by Nigel Charles Andrew Pitman Department of Botany Duke University Date: Approved: _ John W. Terborgh, Supervisor _ _ _ _ Dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Botany in the Graduate School of Duke University ii ABSTRACT (Ecology-Community) A LARGE-SCALE INVENTORY OF TWO AMAZONIAN TREE COMMUNITIES by Nigel...»

«Access to Electronic Thesis Author: Niraj Aswani Thesis title: Evolving a General Framework for Text Alignment: Case Studies with Two Asian Languages Qualification: PhD This electronic thesis is protected by the Copyright, Designs and Patents Act 1988. No reproduction is permitted without consent of the author. It is also protected by the Creative Commons Licence allowing Attributions-Non-commercial-No derivatives. If this electronic thesis has been edited by the author it will be indicated as...»

«Syracuse University School of Social Work 280 White Hall Syracuse, NY 13244 MATTHEW C. SPITZMUELLER, PH.D., LCSW mcspitzm@syr.edu EDUCATION 2014 University of Chicago, Doctor of Philosophy School of Social Service Administration, Chicago, IL 2008 University of Chicago, Master of Social Work School of Social Service Administration, Chicago, IL 2005 University of Chicago, Master of Arts Divinity School, Chicago, IL 1997 Carleton College, Bachelor of Arts Department of Psychology, Northfield, MN...»

«Mónica Sofia Santos Mendes Mestrado em Comunicação Educacional Multimédia Licenciatura em Design de Comunicação ARTiVIS Arts, Real-Time Video and Interactivity for Sustainability Dissertação para obtenção do Grau de Doutor em Media Digitais Orientador: Nuno Manuel Robalo Correia, Professor Catedrático, Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa Co-orientadora: Sílvia Lamy Tavares Chicó, Professora Catedrática, Faculdade de Belas-Artes da Universidade de...»

«Coping with Power Interruptions in Tanzania: An Industrial Perspective A Case Study of One Small Scale Animal Food Processing Industry in Moshi Municipality Theodora Ephrem, KAVISHE A thesis submitted for the partial fulfilment of the requirement for the Master degree of Philosophy in Culture, Environment and Sustainability Centre for Development and Environment UNIVERSITY OF OSLO [Autumn, 2015] © Theodora Ephrem, Kavishe Coping with Power Interruptions in Tanzania: An industrial perspective:...»

«FIRST PRINCIPLES STUDY OF SOME PHYSICAL All Rights Reserved Library of University of Jordan Center of Thesis Deposit PROPERTIES OF TRANSITION METAL MONOSILICIDES By Manal Mohammad AbdulSalam Supervisor Dr Jamil Khalifeh, Prof. Co-Supervisor Dr Abdallah Qteish, Prof. This Dissertation was Submitted in Partial Fulfillment of the Requirements for the Doctor of Philosophy Degree in Physics Faculty of Graduate Studies University of Jordan January, 2006 ‫ﺍﻟﺠﺎﻤﻌﺔ...»

«PEITHO / EXAMINA ANTIQUA 1 ( 4 ) / 2013 Anaximander’s ‘Boundless Nature’ DIRK L. COUPRIE / Amsterdam / RADIM KOČANDRLE / Plzeň / Introduction As Finkelberg1 already said, one of the most obscure terms in Greek philosophy, ascribed to Anaximander, is τὸ ἄπειρον, which may be tentatively translated as ‘the boundless’ (or ‘the infinite’, or ‘the non-finite’; some authors even simply transliterate ‘the apeiron’). The generally accepted opinion is that Anaximander...»

«DEFECT ENGINEERING OF ELECTROCERAMICS: BISMUTH TRIIODIDE AND BARIUM TITANATE By HYUKSU HAN 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 © 2014 HyukSu Han To my future self ACKNOWLEDGMENTS At the very first, I sincerely appreciate my advisor Dr. Juan C. Nino for his support and guidance. His knowledge, care, optimism, diligence, and aspirations inspired me to...»

«Complaining and Arguing in Everyday Conversation by Ian Dersley A Dissertation Submitted to the Department of Sociology for the Degree of Doctor of Philosophy The University of York, Department of Sociology May 1998 Abstract This thesis investigates the formulation of argumentative talk, by adults, in everyday, non-institutional conversational environments. Using the analytical methodology of conversation analysis, I begin by investigating the ways in which responses to complaints are typically...»

«THE IDEAL OF ORTHONOMOUS ACTION, OR: THE HOW AND WHY OF CONSISTENT BUCK-PASSING Michael Smith 1. Two approaches Imagine trying to explain to a group of people what a philosopher is. There are at least two approaches you could take. One would be to describe what an ideal philosopher does: the sorts of questions he thinks about, the methods he uses in answering them, the level of detail and precision he demands of his answers, how he deals with those who disagree with him, and so on. Having fixed...»

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