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

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 19 | 20 || 22 | 23 |   ...   | 27 |

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

-- [ Page 21 ] --

Proof: If c\$ = −∞ then the line y = y \$ intersects all the rays at −∞ and hence for i = 1,..., n, gi (y \$ ) = ai. Suppose y 0 is an optimal solution of the restricted lex1-center problem. From the deﬁnition of functions gi, for i = 1,..., n, gi (y 0 ) ≥ ai, so due to Observation 12.2.2

–  –  –

and that the optimal center is unique, for this case where c\$ is ﬁnite.

12.3 A linear time solution algorithm for the min rays problem As in the previous section, let c\$ and y \$ be an optimal solution for the min rays problem. By using Theorem 12.2.3, p@ = (x@, y \$ ) is an optimal center for the restricted lex1-center problem. We deﬁne a test oracle as follows. The input of the test oracle is the same as for the min rays problem with an additional

point p = (x@, y). The output is one of the following:

• p is an optimal center.

• p is not an optimal center. All optimal centers lie to the right of p (i.e., y \$ y).

• p is not an optimal center. All optimal centers lie to the left of p (i.e., y \$ y).

We ﬁrst show that Lemma 12.3.1 The test oracle can be implemented in linear time.

Proof: We ﬁrst note that, u(y), the upper envelope of the rays in the min rays problem, is a unimodal function, i.e., it has either a unique ﬁnite local minimum which is also its global minimum, or the minimum is −∞ and the source of −∞, u−1 (−∞), is a compact interval. (See [JKP72] pp. 52 for a deﬁnition of unimodal one variable functions).

We compute the value of each of the 2n rays at y. If all the values are −∞ we conclude that p is an optimal center. Else there is a ﬁnite maximal value among the 2n calculated values. We look at the rays attaining this maximal value on y. If all of them are decreasing we conclude that p is not an optimal center and y \$ y. If all of them are increasing we conclude that p is not an optimal center and y \$ y. Else, there are rays of both types and we conclude that p is an optimal center. Clearly, the time consumed in the algorithm given above is linear in n.

We are now ready to prove Theorem 12.3.2 The min rays problem is solvable in Θ(n) time.

–  –  –

the critical values. The value y m can be found in linear time due to Blum, Floyd, Pratt, Rivest and Tarjan [BFPRT73] (see alternatively [CLR90]). At this time we call the test oracle with p = (x@, y m ). This test runs in linear time (Lemma 12.3.1). Suppose ﬁrst that the test oracle returns that p is not an optimal center and that all optimal centers lie to the right of p. The critical values of at least half of the pairs are to the left of y m and hence to the left of any optimal center. Thus we drop one of the rays in each one of these pairs, namely r. If the test oracle returns that p is not an optimal center and that all optimal centers lie to the left of p we act similarly and drop the ray r of at least half of the pairs. In this case we drop at least 4 of the rays.

We process the set of pairs of type (i4) as follows. As before we deﬁne for each pair a critical real value.

This value is the projection on the y axis of the intersection point of the rays composing the pair, as indicated by the big white circle in Figure 12.4 (i4). Now, let y m denote the median of the critical values. At this time we call the test oracle with p = (x@, y m ). Suppose ﬁrst that the test oracle returns that p is not an optimal center and that all optimal centers lie to the right of p. The critical values of at least half of the pairs are to the left of y m and hence to the left of the optimal center. Thus we drop one of the rays in each one of these pairs, namely r. Now suppose that the test oracle returns that p is not an optimal center and that all optimal centers lie to the left of p. The critical values of at least half of the pairs are to the right of y m and hence to the right of the optimal center. We construct a new critical value for each of these pairs as indicated by the small black circle in Figure 12.4 (i4). Now, let y m denote the median of the new critical values. At this time we call the test oracle with p = (x@, y m ). Suppose ﬁrst that the test oracle returns that p is not an optimal center and that all optimal centers lie to the right of p. The critical values of at least half of the pairs are to the left of y m and hence to the left of any optimal center. Thus we drop one of the rays in each one of these pairs, namely r. If the test oracle returns that p is not an optimal center and that all optimal centers lie to the left of p we act similarly and drop the ray r of each one of at least half of the pairs. In this case we drop at least 1 of the rays.

We process the sets of decreasing pairs (d1), (d2), (d3) and (d4) in a symmetric way.

If during the iteration the test oracle returns that p is an optimal center we exit the algorithm and return this point. Otherwise we are left with no more than 8 of the original rays. We arbitrary form pairs of the remaining rays, partition the pairs of rays into the 12 types as before and reiterate until we are left with a constant number of rays. The critical values we associate with these constant number of rays are the projections on the y-axis of their roots and of their intersection points. There is a constant number of such

–  –  –

12.4 A linear time solution algorithm for the lex1-center problem Let p∗ = (x∗, y ∗ ) be an optimal center of the lex1-center problem (12.5). Let c∞ be the solution value of the (non-lexicographic) weighted planar 1-center problem (12.3) and p∞ = (x∞, y ∞ ) be a center realizing this solution.

We observe that if the maximal distance c∞ is realized by an horizontal distance then there exists i such that c∞ = ωi dx (p∞, pi ) ≥ ωi dy (p∞, pi ) and x∗ = x∞. We ﬁnd x∞ by solving Problem (12.3) in linear time as demonstrated in Section 12.1. Next we let x@ = x∞ and ﬁnd an optimal center p@ = (x@, y @ ) for the restricted lex1-center problem by solving the min rays problem in linear time by the algorithm presented in the previous section. Due to Theorem 12.2.3 the solution is an optimal solution for the restricted lex1-center problem.

If the maximal distance c∞ is not realized by an horizontal distance (i.e., it is realized by a vertical distance), we rotate the points in P by π radians around the origin and repeat the above process. We proved Theorem 12.4.1 The lexicographic rectilinear 1-center problem in the plane is solvable in Θ(n) optimal time.

12.5 Concluding remarks We note that our algorithm can be modiﬁed in order to solve, in the same time bound, the following generalizations of the lex1-center problem (with l∞ norm).

• The lex1-center problem in I d. We describe in short the solution algorithm for this problem. As in R the planar problem, we ﬁrst solve the corresponding non-lexicographic 1-center problem. This ﬁxes one of the d coordinates. Then we successively solve d − 1 restricted problems, of decreasing dimensions d − 1, d − 2,..., 1 by decomposing each restricted problem of dimension d into d one-dimensional min rays problems. It thus follows that the total running time is linear in n where the constant is quadratic in d.

–  –  –

• In the all-centers lex1-center problem we are given the same input as for the lex1-center problem.

Instead of ﬁnding an optimal center, one has to ﬁnd all optimal centers.

We now consider another version of the lex1-center problem, the discrete lex1-center problem. In this problem the center must be one of the input points.

The discrete lex1-center problem on the real line is solved in O(n log n) time as follows. Let p∗ be the optimal center of the (non-lexicographic) 1-center problem on the real line. We next ﬁnd the two neighboring points pl, pr ∈ P of p∗. Due to the convexity of the objective function one of pl, pr is an optimal solution. We calculate the lexicographic distances vector from each of pl, pr to the remaining points by ﬁrst calculating the n − 1 distances and then sorting it. We then compare the two vectors. The center realizing the lexicographically smaller vector is an optimal solution. The above operations can be done in O(n log n) total time. We observe that the all-centers discrete non-weighted lex1-center problem on the real line has a lower bound of Ω(n log n) under the algebraic computation tree model by a simple reduction from set equality problem [Be83].

We observe that the discrete lex1-center problem in I d (d ≥ 2) is solved in O(n2 ) time (where the R constant depends exponentially on d) as follows. First construct the n sorted weighted distances vectors from each point in P to all the remaining n − 1 points. This is done by a reduction to the O(n2 ) algorithm of Lee and Ching [LC85] which sorts the n sets of directions from each point in an n-membered set of points in the plane, to the remaining points. The optimal center is the point which realizes the lexicographically smallest vector among the resulting n sorted vectors.

Chapter 13 Concluding remarks [A94] concludes her paper with “...The major open problem is to characterize the Helly systems (X, H) for which there is an objective function ω that gives a ﬁxed dimensional LP-type1 problem (H, ω)”. A partial answer for her question is that every lexicographic Helly system (see Subsection 2.3.3) admits an objective function ω that gives a ﬁxed dimensional LP-type problem (H, ω).

In her thesis ([A93]), Amenta explores the class of LP-type problems and its intimate relationship with Helly theorems. She summarizes her theoretical results as

Helly ⊃ LP-type ⊃ CP

that is, the class of problems for which there is a Helly theorem about the constraints, strictly contains the class of ﬁxed-dimensional LP-type problems, which strictly contains the class of CP, convex programming problems.

Let LexHelly denote the class of problems for which there is a lexicographic Helly theorem about the constraints. In this thesis we show that LexHelly ⊂ Helly and that LexHelly ⊆ LP-type.

We also deﬁne discrete Helly theorems, lex-discrete Helly theorems and discrete LP-type problems and show that the class of problems for which there is a lex-discrete Helly theorem about the constraints equals the class of ﬁxed-dimensional discrete LP-type problems. We provide linear time random algorithms for solving ﬁxed-dimensional discrete LP-type problems which satisfy the Violation Condition (Deﬁnition 3.3.15). It is an open problem to provide such algorithms without using the Violation Condition.

In Chapter 11 we formulate the simple stochastic game decision problem as a discrete LP-type problem, and solve it in subexponential time by using the LP-type algorithm of [SW92]. It is an interesting open problem whether more games, for which no subexponential algorithm is currently known, can be formulated as discrete LP-type problems, LP-type problems, or even Linear Programming problems.

Similarly to the continuous case, the connection between discrete Helly theorems and discrete LP-type theory has been mutually proﬁtable. We have proved a few lex-discrete Helly theorems by showing that the discrete abstract problem corresponding to it has a deﬁning set of ﬁxed cardinality (Theorem 4.2.5). Going in 1 Amenta uses the term GLP rather than LP-type.

the other direction, we have showed several geometric optimization problems to be discrete LP-type problems by using discrete Helly theorems.

In this thesis we obtain more than a dozen new discrete, lexicographic and lex-discrete Helly theorems.

We strongly believe that further research will lead to the discovery of more such Helly theorems.

Appendix A Proving theorems related to line transversals A.1 Discrete and lex variants of Theorem 2.1.4 (Theorems 2.2.7, 2.3.7 and 2.4.3) We start by proving a lex-discrete version of Theorem 2.1.4 Proof: (of Theorem 2.4.3) We can assume that ∀a ∈ S, a ≤ a (otherwise we drop from S all slopes greater from a without aﬀecting the theorem). Every non-vertical line in the plane has a real (ﬁnite) slope.

For every pair of two convex sets di and dj from D we denote by (di, dj ) the closed interval of slopes, such that for every a ∈ (di, dj ) there exists a line transversal for di and dj with slope a. Since every 4 sets admit a line transversal with slope from S, every two of these intervals have a common point from S. Hence, due to Theorem 2.2.1, there exists a slope a ∈ S such that each two sets from D admit a common transversal y = ax + b for some b. Let a ∈ S 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 quadruple of objects, that there exists a common line transversal y = a x + b, for dk, di, dj with b ≤ b, so seg[k] ∩ (−∞, b ] = ∅ as needed.

Considering Theorem 2.2.7, we assume that a separating direction is the y-axis (otherwise we rotate the plane relatively to the origin and update S accordingly). Due to Observation 2.4.8 the Helly number of Theorem 2.2.7 is bounded above by the one of its lexicographic version, Theorem 2.4.3, i.e., 4.

The Helly number 4 is tight for Theorem 2.2.7, since Theorem 2.2.10(i), which is a special case of Theorem 2.2.7, has Helly number 4. We now prove a lexicographic (continuous) version of Theorem 2.1.4 Proof: (of Theorem 2.3.7) The proof resembles the one of Theorem 2.4.3.

Pages:     | 1 |   ...   | 19 | 20 || 22 | 23 |   ...   | 27 |

Similar works:

«Doubt, Faith, and the World to Come in Peter of Cornwall’s Book of Revelations By Michael D. Barbezat A thesis submitted in conformity with the requirements for the degree of Doctor of Philosophy Center for Medieval Studies University of Toronto © Copyright by Michael D. Barbezat 2013 Doubt, Faith, and the World to Come in Peter of Cornwall’s Book of Revelations Michael D. Barbezat Doctor of Philosophy Centre for Medieval Studies University of Toronto Abstract This dissertation explores...»

«THE GAME WITH MINUTES Frank C. Laubach CHRIST IS THE ONLY HOPE OF THE WORLD ‘Disillusioned by all our other efforts, we now see that the only hope left for the human race is to become like Christ.’ That is the statement of a famous scientist, and is being repeated among ever more educators, statesmen, and philosophers. Yet Christ has not saved the world from its present terrifying dilemma. The reason is obvious: few people are getting enough of Christ to save either themselves or the world....»

«Alte Mythen – neue Gesichter: Melancholie und Weiblichkeit im Wandel (1850-2005) Dissertation zur Erlangung des akademischen Grades eines Dr. phil. der Philosophischen Fakultät der Universität des Saarlandes vorgelegt von Lydia Reuther Saarbrücken Februar 2009 Erstgutachter: Prof. Dr. Manfred Schmeling Zweitgutachter: Dr. Jutta Ernst Aus dem Widerspruch von Endlichkeit und Unendlichkeit, von Begrenztheit und Unbegrenztheit erwächst die Melancholie. Es liegt darin die Chance, zu einem...»

«ELEMENTARY PRINCIPAL EMOTIONAL INTELLIGENCE, LEADERSHIP BEHAVIOR, AND OPENNESS: AN EXPLORATORY STUDY DISSERTATION Presented in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in the Graduate School of The Ohio State University By Thomas G. Reed, B.S., M.S. **** The Ohio State University Dissertation Committee: Approved by Professor Wayne K. Hoy Professor Anita Woolfolk Hoy _ Professor Scott Sweetland Advisor Professor Nancy Nestor-Baker College of Education...»

«On the Functions of Morality by Aryn Ashley Conrad Department of Philosophy Duke University Approved: Karen Neander, Supervisor David Wong Owen Flanagan Robert Brandon Alex Rosenberg Jennifer Hawkins Dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Philosophy in the Graduate School of Duke University ABSTRACT On the Functions of Morality by Aryn Ashley Conrad Department of Philosophy Duke University Approved:...»

«©2009 Irene Lopatovska ALL RIGHTS RESERVED EMOTIONAL ASPECTS OF THE ONLINE INFORMATION RETRIEVAL PROCESS by IRENE LOPATOVSKA A Dissertation submitted to the Graduate School – New Brunswick Rutgers, The State University of New Jersey In partial fulfillment of the requirements For the degree of Doctor of Philosophy Graduate Program in School of Communication, Information and Library Studies Written under the direction of Professor Nicholas J. Belkin And approved by New Brunswick, New...»

«UNIVERSITY OF CALGARY Changes in tendon compliance and muscle energetics of in vivo human skeletal muscle by Jared R Fletcher A THESIS SUBMITTED TO THE FACULTY OF GRADUATE STUDIES IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY GRADUATE PROGRAM IN KINESIOLOGY CALGARY, ALBERTA DECEMBER, 2014 © Jared R Fletcher 2014 Abstract Recently published reports suggest the role of the muscles and tendons of the lower limbs are an important factor in determining the energy...»

«BIT PERMUTATION INSTRUCTIONS: ARCHITECTURE, IMPLEMENTATION, AND CRYPTOGRAPHIC PROPERTIES Zhijie Jerry Shi A DISSERTATION PRESENTED TO THE FACULTY OF PRINCETON UNIVERSITY IN CANDIDACY FOR THE DEGREE OF DOCTOR OF PHILOSOPHY RECOMMENDED FOR ACCEPTANCE BY THE DEPARTMENT OF ELECTRICAL ENGINEERING June 2004 UMI Number: 3120436 Copyright 2004 by Shi, Zhijie Jerry All rights reserved. UMI Microform 3120436 Copyright 2004 ProQuest Information and Learning Company. All rights reserved. This microform...»

«Stony Brook University The official electronic file of this thesis or dissertation is maintained by the University Libraries on behalf of The Graduate School at Stony Brook University. © Allll Riightts Reserved by Autthor. © A R gh s Reserved by Au hor The Household Meals Project: Feeding Power A Dissertation Presented by Carol Shepherd Lindquist to The Graduate School in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in Sociology Stony Brook University May...»

«Ethical Consumerism: everyday negotiations in the construction of an ethical self by Tracey Bedford Thesis submitted in fulfilment of the requirements for the degree of Doctor of Philosophy University College London Abstract Despite market research findings which assert that up to 90% of all consumers believe that ethical issues are an important consideration when purchasing products, estimates of the number of people consuming ethically with any regularity remain at around 1%. The aim of this...»

«2011 – 2012 Teacher Credentialing/Master’s Program Student Handbook Multiple Subject TABLE OF CONTENTS 1. PROGRAM PHILOSOPHY AND EMPHASIS 2. TYPE OF TEACHING CREDENTIAL YOU WILL EARN Multiple Subject Multiple Subject with BCLAD Additional Authorizations Supplementary Authorizations Subject Matter Authorizations Adding a Single Subject Authorization 3. COMPLETING PROGRAM PREREQUISITES 4. GETTING READY FOR THE CREDENTIAL YEAR Certificate of Clearance Establishing a UCD Computer Account Degree...»

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

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