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

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 20 | 21 || 23 | 24 |   ...   | 27 |

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

-- [ Page 22 ] --

We ﬁrst assume that the following condition holds. In the last paragraph in the proof we will show that this condition is always met. The condition is that each two of the intervals (di, dj ) (deﬁned in the proof of Theorem 2.4.

3 above) have a common point not greater than a. Hence, due to the lexicographic version of Helly’s Theorem, Theorem 2.3.2, there exists a slope a ≤ a such that each two sets from D admit a common transversal with slope a. Let a be the minimal such slope.

For every dk ∈ D we denote by seg[k] the interval resulted by the intersection of the y-axis with all the line transversals with slope a that dk admits. Since each two sets from D admit a common transversal with slope a, the intervals in {seg[k] | dk ∈ D} are pairwise intersecting. Due to Helly’s Theorem, there exists a point b common to all the intervals. Let b be the minimal such b. In other words the line y = a x + b is a line transversal for D. If a a then (a, b ) L (a, b ) and we are done.

Otherwise (a = a ), we need to show that b ≤ b, i.e., ∀k, seg[k] ∩ (−∞, b ] = ∅. Since a = a there exists an interval of slopes (di, dj ) whose minimal slope is a. Let us consider the interval of slopes of all the line transversals for dk, di, dj. The minimal slope in the interval is a. This implies together with the theorem’s assumption about triplets of objects, that there exist a common line transversal y = a x + b, for dk, di, dj which have b ≤ b, so seg[k] ∩ (−∞, b ] = ∅ as needed.

It remains to show that each two intervals of slopes have a common point not greater than a. We use similar arguments as in the proof of Theorem 2.1.4. For such pairs of intervals as (di1, di2 ) and (di1, di3 ) this is assured by the assumption of a common transversal of slope at most a for di1, di2 and di3. We now show that each two intervals, say (di1, di2 ) and (di3, di4 ) have a common point of at most a. Due to the theorem’s assumption the minimal slope for each one of these two intervals is at most a, so if they have a common point, they must have also a common point of at most a. Hence it is suﬃcient to show that these intervals have a common point. If these intervals, (di1, di2 ) and (di3, di4 ), do not have a common point, then a contradiction would result as follows. Each of the intervals (di1, di3 ), (di1, di4 ), (di2, di3 ) and (di2, di4 ) would have points in common with both (di1, di2 ) and (di3, di4 ), so that the following situation arises for a slope a∗ between (di1, di2 ) and (di3, di4 ): the convex sets di1, di2 and also di3, di4, are separable by lines of slope a∗, from which follows the separability of an additional pair by means of each of these two separating lines, but the pairs di1 and di3, di1 and di4, di2 and di3, and di2 and di4 are not separable in this way. This is obviously a contradiction.

The Helly number 3 is tight due to Observation 2.3.12 and Theorem 2.1.4.

A.2 Discrete and lex variants of Theorem 2.1.8 (Theorems 2.2.10, 2.3.10 and 2.4.6) We start by presenting an alternate proof for Theorem 2.1.8(i). This proof will be helpful in proving more discrete Helly theorems for line transversals later in this chapter. We use a well known (see for example [Ed87]) geometric duality transformation Deﬁnition A.2.1 Let D be a transformation which maps every point (a, b) in the plane into the non vertical line y = ax − b and vice versa, that is, it maps a non vertical line l to the point D(l) such that D(D(l)) = l.

Let h ⊂ I 2 be a set of points. We extend the deﬁnition of D to sets of points in the natural way D(h) = R {D(p) | p ∈ h}.

We note

–  –  –

Observation A.2.3 D transforms every vertical interval [(a, b), (a, b )] into a strip with slope a, which intersects the y-axis in the interval [(0, −b ), (0, −b)] and transforms the set of all lines with slope a into the vertical line x = a.

Considering an axis-parallel rectangle as an (inﬁnite) union of vertical intervals we get Observation A.2.4 D transforms every axis-parallel rectangle h into an unbounded non-convex polygon D(h), which is the complement of the union of two disjoint unbounded convex polygons. The intersection of D(h) with either one of the x non-positive or the x non-negative halfplanes yields a convex unbounded polygon (see Figure A.1).

Proof: (of Theorem 2.1.8(i)) We assume without loss of generality that the segments are vertical (we can rotate the segments in D around the origin). We use the duality transformation D deﬁned above and consider the corresponding dual problem. Due to Observation A.2.3, each vertical line in the primal is transformed to a strip in the dual. Since the resulting strips are convex sets, we get from Helly’s Theorem that if every 3 strips intersect then all strips intersect. Every point in this intersection equals in the primal problem to a line transversal which intersects H.

This Helly number cannot be reduced to two (consider for instance any 3 non-collinear points in the plane).

Using in the proof above the lexicographic version of Helly’s Theorem, implies an upper bound of 3 for the lexicographic Helly number in Theorem 2.3.10(i). By Observation 2.3.12, the lexicographic Helly number in Theorem 2.3.

10(i) is at least as large as the Helly number of its non-lexicographic version, Theorem 2.1.8(i), so it is exactly 3. We now prove a discrete version of Theorem 2.1.8(i) Proof: (of Theorem 2.2.10(i)) Without loss of generality we assume that the segments are vertical (otherwise we rotate the segments in D around the origin and update S accordingly). If there is no line transversal for D, by Theorem 2.1.8(i) there are 3 translates in D for which there is no line transversal.

Otherwise (there exists a line transversal for D), we use the duality transformation D from Deﬁnition A.2.1 and consider the corresponding dual problem. Due to Observation A.2.3, for every d ∈ D, D(d) is a strip.

The intersection of these strips forms a non-empty polygon P = ∩d∈D D(d). We let P be the polygon containing P, which is resulted by the intersection of the following at most 4 diﬀerent strips. Two strips whose intersection has the same rightmost point as of P, and two strips whose intersection has the same

–  –  –

leftmost point as of P. Observations A.2.3 and A.2.2 imply that a line transversal of D with direction in S exists if and only if there is an intersection between P and some vertical line in D(S).

It is clear from the following example that the Helly number cannot be reduced to 3 Example A.2.5 Let D = {a, b, c, d} consists of the vertical 2-units intervals a = [(−1.5, 1); (−1.5, 3)], b = [(−1, 2); (−1, 4)], c = [(1, 2); (1, 4)] and d = [(1.5, 3); (1.5, 5)] (see left side of Figure A.2) and let S = {s1 = −0.1, s2 = 1.1} be the set of line directions (each direction is represented by a real number). The set of line transversals for each interval is a strip in the dual (see right side of Figure A.2). The feasible region of line transversals is the intersection of the 4 strips D(a), D(b), D(c), D(D), i.e., the quadrangle whose corners are the white points in the ﬁgure. The set of line transversals with directions in S are the two thick vertical lines D(s1 ), D(s2 ). We note that the quadrangle does not intersect either of the lines D(s1 ), D(s2 ), while the intersection of each three strips intersects one of the two vertical lines.

–  –  –

The deﬁnition of ω together with Observation A.2.2 implies that for every a, b ∈ I and (D, S ) ∈ 2D × 2S, R the intervals 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.

If there is no line transversal for D with direction in S, by Theorem 2.2.10(i) there are 4 translates in D for which there is no line transversal with direction in S. We set D to consist of these translates.

Otherwise, the convex polygon P = ∩d ∈D D(d ) is not empty. Observation A.2.2 implies that D admits a line transversal y = ax + b with (a, b) ≤L (a, b ) if and only if P contains the point (a, b). Let dl, dl ∈ D be vertical intervals, such that the left intersection point of D(dl ), D(dl ) equals the leftmost point of P.

Similarly, let dr, dr ∈ D be vertical intervals, such that the right intersection point of D(dr ), D(dr ) equals the rightmost point of P.

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

Otherwise, let a ∈ S be the smallest slope such that P intersects the line x = a. We let d∗ ∈ D be a vertical interval, such that the intersection point (a, y ), of the strip D(d∗ ) and the line x = a, has the highest y. We set D = {dl, dl, d∗ }.

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

Choosing a arbitrary large, say a = 10, and any real b for Example A.2.5, we get that the Helly number cannot be reduced to 3.

We note that Theorem 2.4.6(i) implies Theorem 2.2.10(i) in the following way. Due to Observation 2.4.8 the Helly number in Theorem 2.2.10(i) is bounded from above by 4, the Helly number in Theorem 2.4.6(i).

Due to Example A.2.5 it is at least 4, so it is 4.

We now prove a lexicographic version of Theorem 2.1.8(iii),(iv) by using Theorem 4.1.6 Proof: (of Theorem 2.3.10(iii),(iv)) We will use the duality transformation D from Deﬁnition A.2.1.

Let ω : 2H →I 2 ∪ {∞} be a function such that for every H ⊆ H, ω(H ) is the lexicographically smallest R point in ∩h∈H D(h ), 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 H ⊆ H, the rectangles in H are met by a common R line y = ax + b with (a, b) ≤L (a, b ) if and only if ω(H ) ≤L (a, b ). Moreover, since set intersection is monotone (i.e., A ∩ B ⊆ A, B), (H, ω) is an abstract problem which meets the Monotonicity Condition.

Hence, due to Theorem 4.1.6, it is suﬃcient to show that for every H ⊆ H, there exists a solution deﬁning set H of cardinality at most 5.

If there is no line transversal for H, by Theorem 2.1.8(v) there are at most 5 translates in H which do not admit a common line transversal. We set H to consist of these translates.

Otherwise, H admits a line transversal. Due to Observation A.2.4 the intersection of ∩h∈H D(h) with the x non-negative halfplane (the x non-positive halfplane) is a (possibly empty) convex polygon P+ (P− ), respectively. If P− is not empty, there exist at most two translates h1, h2 ∈ H which determine the lexicographically smallest point in P− (i.e., lexicographic min P− = lexicographic min(D(h1 ) ∩ D(h2 ))). We set H = {h1, h2 }.

Otherwise (P− is empty and P+ is not empty), due to Helly’s Theorem there exists a set H ⊆ H of cardinality at most 3 such that (I + ×I R)∩(∩h∈H D(h)) = ∅. Moreover, since P+ is not empty there exist at R most two translates h1, h2 ∈ H which determine the lexicographically smallest point in P+ (i.e., lexicographic min P+ = lexicographic min((I + × I ∩ D(h1 ) ∩ D(h2 ))). In this case we set H = H ∪ {h1, h2 }.

R R) In all cases, H is a solution deﬁning set for H with cardinality at most 5, as required.

From Observation 2.4.8 and the fact that the Helly number of the corresponding non-lexicographic Helly theorem, Theorem 2.1.8(iii),(iv), is 5, we get that the Helly number cannot be reduced to 4. We now prove a lex-discrete version of Theorem 2.1.8(iii),(iv) using Theorem 4.2.5 Proof: (of Theorem 2.4.6(iii),(iv)) 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 lexiR cographically 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 R D S (D, S ) ∈ 2 × 2, 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 | ≤ 7.

We ﬁrst consider the case where D admits a line transversal. Let P+ (P− ) denote the intersection of ∩d ∈D D(d ) with the x non-negative (the x non-positive) halfplane, respectively. Due to Observation A.2.4, P+ and P− are (possibly empty) convex polygons.

For X = P−, P+, let dl (X), dl (X) ∈ D be rectangles such that the leftmost intersection point of D(dl ), D(dl ) equals the leftmost point in X. Similarly, let dr (X), dr (X) ∈ D be such that the rightmost intersection point of D(dr ), D(dr ) equals the rightmost point in X. In this way at most 8 rectangles determine the leftmost and rightmost extreme points in P− and P+.

Observations A.2.2 and A.2.3, and the deﬁnition of P+ and P− imply that D admits a line transversal with direction in S if and only if the intersection between P+ ∪ P− and D(S ) is not empty. By making a more careful analysis, which takes into consideration the fact that the objects in D are pairwise disjoint translates of a rectangle, we will show that the leftmost and rightmost points in P+ and P− are determined by at most 7 polygons. I.e., we can choose {dl (P− ), dl (P− ), dr (P− ), dr (P− ), dl (P+ ), dl (P+ ), dr (P+ ), dr (P+ )} such that the set is of cardinality at most 7.

Pages:     | 1 |   ...   | 20 | 21 || 23 | 24 |   ...   | 27 |

Similar works:

«1 BLACKBOARD NOTES ON NOZICK VERSUS SEN PHILOSOPHY 167 SPRING, 2007 ROBERT NOZICK ON RIGHTS AS SIDE CONSTRAINTS. Moral rights should be conceived as side constraints on actions not as goals to be promoted. We ought always to respect rights (that is, refrain from violating them ourselves), not act to maximize their overall fulfillment. On the side constraint view, a right should enter the determination of what one morally ought to do in this way: Of the acts one could do at a given time,...»

«ABSTRACT Title of Dissertation GLOBAL CAPITALISM MEETS LOCAL POSTCOMMUNISM: TENSIONS IN TRANSITION AS MANIFESTED THROUGH PHYSICAL CULTURE AND THE FEMALE BODY IN ROMANIA Jessica W. Chin, Doctor of Philosophy, 2008 Dissertation directed by: Dr. David L. Andrews Department of Kinesiology Nearly two decades after communism officially ended in Romania, the nation continues to struggle in its transition from state socialism to liberal democracy. The increased presence and influence of Western images,...»

«CERIAS Tech Report 2009-31 Effects of Anonymity, Pre-Employment Integrity and Antisocial Behavior on Self-Reported Cyber Crime Engagement: An Exploratory Study by Ibrahim M. Baggili Center for Education and Research Information Assurance and Security Purdue University, West Lafayette, IN 47907-2086 Graduate School ETD Form 9 (Revised 12/07) PURDUE UNIVERSITY GRADUATE SCHOOL Thesis/Dissertation Acceptance This is to certify that the thesis/dissertation prepared By Ibrahim Baggili Entitled...»

«THE BIBLICAL SIGNIFICANCE OF JABAL AL LAWZ A Dissertation Presented to the Faculty of Louisiana Baptist University In Partial Fulfillment of the Requirements for Doctor of Philosophy In Bible and Theology By Charles A. Whittaker May 2003 ABSTRACT This dissertation is concerned with exposing the Biblical significance of a mountain in the northwest corner of Saudi Arabia. The mountain is Jabal al Lawz and it is significant because it is the conclusion of this paper that it is the best candidate...»

«THESIS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in Machine and Vehicle Systems Integrated Pedestrian Safety Assessment A Method to Evaluate Combinations of Active and Passive Safety Systems NILS LÜBBE Department of Applied Mechanics CHALMERS UNIVERSITY OF TECHNOLOGY Gothenburg, Sweden, 2015 Integrated Pedestrian Safety Assessment A Method to Evaluate Combinations of Active and Passive Safety Systems NILS LÜBBE ISBN 978-91-7597-296-1 © NILS LÜBBE, 2015 Doktorsavhandlingar vid Chalmers tekniska...»

«Marketing Networks 2.0 Andrew T. Stephen Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy under the Executive Committee of the Graduate School of Arts and Sciences COLUMBIA UNIVERSITY UMI Number: 3373532 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...»

«PHOSPHORUS SORPTION AND DESORPTION IN A BRAZILIAN ULTISOL: EFFECTS OF pH AND ORGANIC ANIONS ON PHOSPHORUS BIOAVAILABILITY By SHINJIRO SATO 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 2003 by Shinjiro Sato This Ph.D. dissertation is dedicated to my life mentor, Dr. Daisaku Ikeda; and to all men, women, and children in the Amazon. ACKNOWLEDGMENTS It is...»

«THE ―DEAR DIANE‖ LETTERS AND THE ENCOUNTER OF CHINESE YOUNG WOMEN IN CONTEMPORARY AMERICA By Copyright 2012 Hong Cai Submitted to the graduate degree program in American Studies and the Graduate Faculty of the University of Kansas in partial fulfillment of the requirements for the degree of Doctor of Philosophy. Chairperson, David M. Katzman, Ph.D. Co-Chair, Cheryl B. Lester, Ph.D. Norman R. Yetman, Ph.D. William M. Tuttle, Jr., Ph.D. Antha Cotton-Spreckelmeyer, Ph.D. J.Megan Greene,...»

«A Study of Chemotherapy Resistance in Acute Myeloid Leukemia A DISSERTATION SUBMITTED TO THE FACULTY OF THE GRADUATE SCHOOL OF THE UNIVERSITY OF MINNESOTA BY Susan Kay Rathe IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY David A. Largaespada October, 2013     © Susan Kay Rathe 2013     Acknowledgements Funding: The leukemia research was funded by The Leukemia & Lymphoma Society (grant 7019-04). The MMuFLR workflow was funded by The Children's Cancer...»

«Crowd Dynamics G. Keith Still PhD Thesis University of Warwick August 2000 Crowd Dynamics by G. Keith Still BSc Physical Sciences (Robert Gordons Institute of Technology, Aberdeen 1981) A thesis submitted in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Mathematics University of Warwick, Department of Mathematics August 2000 Acknow ledgments Although a few words do not do justice to their contribution I would like to thank the following people for making this...»

«THE RELATIONSHIP BETWEEN CAREGIVER INTIMATE PARTNER VIOLENCE, POSTTRAUMATIC STRESS, CHILD COGNITIVE SELF-DEVELOPMENT, AND TREATMENT ATTRITION AMONG CHILD SEXUAL ABUSE VICTIMS by LEIGH DE ARMAS DELORENZI B.S University of Miami, 2003 M.A. Rollins College, 2009 A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the College of Education at the University of Central Florida Summer Term Major Professor: Andrew P. Daire © 2012 Leigh de Armas...»

«Thermal evolution in sedimentary basins above large shear zones and detachments By Alban Souche Thesis submitted for the degree of Philosophiae Doctor Faculty of Mathematics and Natural Sciences – Department of Geosciences University of Oslo, Norway August 2012 © Alban Souche, 2012 Series of dissertations submitted to the Faculty of Mathematics and Natural Sciences, University of Oslo No. 1254 ISSN 1501-7710 All rights reserved. No part of this publication may be reproduced or transmitted,...»

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