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

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 14 | 15 || 17 | 18 |   ...   | 27 |

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

-- [ Page 16 ] --

tvS be the time needed for checking whether a given s-element violates a given basis B.

tbDS be the time needed for constructing a basis for a given d-element and sets D, S of constant size.

tvD is constant by checking whether the conditions stated in Lemma 9.1.5 are satisﬁed. tvS is constant by checking whether the conditions stated in Lemma 9.1.7 and Lemma 9.1.9 are satisﬁed. tbDS is constant by trying all possible choices of a D ⊆ D, |D | ≤ p + 1 and S ⊆ S, |S | ≤ p and checking whether (D, S ) meets all the conditions as stated in the deﬁnition of a basis (Deﬁnition 3.3.5).

We conclude with Theorem 9.1.15 The discrete p-center problem on the line can be solved in randomized linear time.

We note that all our results remain valid when we omit the general position assumption, by using the “lexicographic” deﬁnition d(x, y) = (|x − y|, min{x, y}).

9.2 p-center problems on circles In this kind of p-center problems the space is a circle (1-dimensional sphere) and the metric is such that the length between two points is the length of the shorter arc between them. We emphasis that the relative order of the points on the circle is not given a-priori.

9.2.1 Continuous case Lemma 9.2.

1 The Helly number of the Helly theorem corresponding to the (continuous) p-center problem on circles is unbounded.

Proof: It is enough to construct for every constant k an instance (H, ω) of the p-center problem on circles such that for every H ⊂ H with |H | ≤ (2k + 1)p, we have ω(H ) ≤ k but ω(H) = k + 1. We achieve this by letting H = {0, 1, 2, 3,..., (2k + 1)p} and making the circle be of perimeter (2k + 1)p + 1.

To conclude this subsection we provide a lower bound of Ω(n log n) for the (continuous) 1-center problem on circles. We will make a reduction from the following problem Problem: Maximum Gap Given n real numbers x1,..., xn, ﬁnd the maximum diﬀerence between two consecutive numbers. (Two numbers xi and xj are said to be consecutive if xi ≤ xj and there exists no other number xk, s.t. xi xk xj.) Lemma 9.2.

2 ([LW86]) The Maximum Gap problem requires Ω(n log n) time under the algebraic computation tree model.

Lemma 9.2.

3 The (continuous) 1-center problem on circles requires Ω(n log n) time under the algebraic computation tree model.

Proof: We show that the Maximum Gap problem can be reduced to the 1-center problem on circles in O(n) time. Given an instance H of the Max Gap problem, we ﬁrst ﬁnd minH and maxH in linear time.

We then deﬁne an instance for the 1-center problem on circles H = {h − minH | h ∈ H} on a circle of perimeter maxH − minH. It is obvious that the maximum gap between two consecutive points in H is maxH − minH −2r1 (H ) where r1 (H ) is the radius of the 1-center problem on H. Therefore the (continuous) 1-center problem on circles also requires Ω(n log n) time.

9.2.2 Discrete case Lemma 9.2.

4 The d-Helly number of the Helly theorem corresponding to the discrete p-center problem on circles is unbounded.

Proof: We use the same construction as in the proof of Lemma 9.2.1 and deﬁne D = S = H. Let D be an arbitrary subset of D such that |D | = (2k + 1)p. It is easy to see that ω(D, S) = k + 1 while ω(D, S) = k.

We conclude this subsection by giving a lower bound of Ω(n log n) for the discrete 2-center problem on circles. We will make a reduction from Set Equality problem (see deﬁnition and lower bound in Section 7.3.1).

Lemma 9.2.

5 The discrete 2-center problem on circles requires Ω(n log n) time under the algebraic computation tree model.

Proof: We show that Set Equality can be reduced to the discrete 2-center problem on circles in O(n) time. Given an instance A, B of the Set Equality problem, we ﬁrst ﬁnd minA and minB in linear time. If minA = minB we stop and output A = B. Otherwise we transform every a ∈ A and b ∈ B into two points on the unit circle in the plane as follows. We transform every a ∈ A into the two intersection points between the unit circle and the line y = (a − minA )x. We transform every b ∈ B into the two intersection points between the unit circle and the line resulted by rotating the line y = (b − minA )x by π radians relatively to the origin. Considering the unit circle as a circle of perimeter 2π, it is easy to see that A = B if and only if the radius of the discrete 2-center problem is π. (If there exists a ∈ A such that a ∈ B, choosing its image / on the unit circle to be the two centers will yield a smaller radius). Therefore the discrete 2-center problem on circles also requires Ω(n log n) time.

9.3 p-center problems with l∞ norm We will mainly concentrate on the planer case where the continuous (discrete) problem is to ﬁnd p congruent squares with edges parallel to the axis (with centers from S), of the smallest radius covering H (D), respectively.

9.3.1 Continuous case The weighted 1-center problem in I d has a linear time solution as it can be formulated as a linear programR ming problem (see [FW74]).

[Dr87] solves in linear time the planar 2-center problem. The weighted 2-center problem has a linear time solution due to [KC92]. Sharir and Welzl ([SW96]) solve in randomized linear time the planar 2-center (3-center) problem by formulating it as a 13-dimensional (43-dimensional) LP-type problem, respectively.

For both problems [SW96] deﬁne explicitly a lexicographic objective function which satisﬁes the Unique Minimum Condition.

The Helly theorem corresponding to the continuous p-center problems with l∞ norm is just Theorem 2.1.2.

We conclude by stating the lower bounds given by Sharir and Welzl Lemma 9.3.

1 ([SW96]) The continuous planar p-center problem with l∞ norm requires Ω(n log n) time under the algebraic computation tree model, for any p 3.

9.3.2 Lexicographic planar case In the lexicographic weighted p-center problem (p-lcenter problem, in short) we are given the same input, and r wish to ﬁnd the lsmallest vector (r, x1, y1,..., xp, yp ) such that the set of all squares { wi hi | i = 1,..., n} with center in H and radius r multiplied by the corresponding weight is ((x1, y1 ), (x2, y2 ),..., (xp, yp ))-p-pierceable.

We call r the radius and (x1, y1,..., xp, yp ) the centers vector. (See Subsection 2.3.2 for deﬁnitions related to p-pierceability.) In this subsection we solve the planar lexicographic weighted p-center problem for p = 1, 2, 3 in randomized linear time by using either

• Theorem 2.1.2, its corresponding lexicographic version Theorem 2.3.4, and Theorem 5.3.6, or

• Theorem 2.1.2 applied on open rectangles, its corresponding lexicographic version Theorem 2.3.4, and Theorem 5.3.7.

Considering the ﬁrst approach, we start by deﬁning the parameterized Helly system corresponding to our problem. Let the ground set of all possible p-centers be

–  –  –

is the set of all points in Xp such that the i-th center is at weighted distance at most λ from h. From the construction we obtain Observation 9.3.2 The solution of the weighted planar p-center problem with l∞ norm on a set of points H = {h1,..., hn } and a corresponding set of weights {ω1,..., ωn } is at most r if and only if there is a common point to all the sets hpr, h ∈ H.

–  –  –

¯ (Hp, ω) is an LP-type problem of combinatorial dimension 2 (6, 34) for p = 1 (p = 2, 3), respectively. In this way the second approach yields LP-type formulations with smaller combinatorial dimension than the ﬁrst approach. These formulations have also smaller combinatorial dimension than the formulation of [SW96] (6 instead of 13 for the case p = 2, and 34 instead of 43 for the case p = 3).

Theorem 9.3.

3 The lexicographic weighted planar p-center problem with l∞ norm is solvable in randomized linear time, for p = 1, 2, 3.

Proof: Until now we have shown that the lexicographic planar p-center problem with l∞ norm is an LP-type problem of dimension at most 2 (6, 34) for p = 1 (p = 2, 3), respectively. We solve this problem by using the LP-type randomized algorithms, such as the one of Sharir and Welzl (see Section 6.2). In order to obtain a linear running time it remains to show how to implement the violation test and basis calculation primitives such that they run in constant time. We slightly change the structure of these two primitives: We implement the basis calculation primitives such that when called with input (B, h) it returns in addition to a basis B(B ∪ {h}) for B ∪ {h}, also the value ω(B ∪ {h}), of the objective function on B ∪ {h}, and the point x(B ∪ {h}) which realizes this value (there is only such point since the objective function is lexicographic).

The input for the violation tests consists of x(B) in addition to B (i.e., we call Violation(B, h, x(B))). The ¯ ¯ violation test primitive checks whether x(B) ∈ hp (h). This is done in constant time since hp (h) is of constant complexity. We implement the basis calculation primitive Basis(B, h) in constant time as follows. For any proper subset B ⊂ B ∪ {h} we calculate explicitly ω(B ) and the point x(B ) realizing this value. Then for every h ∈ B ∪ {h} \ B we call Violation(B, h, x(B )). B is a basis for B ∪ {h} if and only if all these calls return “false”.

We note that since the optimal solution for the lexicographic planar p-center problem is an optimal solution for the non-lexicographic problem, we get an alternative solution to the one of [SW96]. We summarize in Corollary 9.3.4 The planar p-center problem with l∞ norm is solvable in randomized linear time, for p = 1, 2, 3.

–  –  –

with x ≤L x if and only if ω(D, S ) ≤L x. 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 | ≤ 2d.

If D is inﬁnite (then S must be ﬁnite), we replace each box h ∈ D, by the smallest possible compact box C(h) which is contained in h and contains the same points in S as does h. Since the set S is ﬁnite, we get that the resulted set of boxes C(D) = {C(h) | h ∈ D} is also ﬁnite, and for every D ⊆ D and S ⊆ S, ω(D, S ) = ω(C(D ), S ).

If the intersection of the boxes in D is empty, by Theorem 2.1.2(i) there are two boxes which do not intersect. We let D to consist of these two boxes.

Otherwise, for each coordinate i = 1,..., d, we act as follows. Let Li (D ) ∈ D be a box whose projection on the i’th coordinate is an interval [li, ri ] with the smallest ri (if D is inﬁnite, such a box does not necessarily exist. In this case we take instead a box h ∈ D such that C(h) ∈ C(D ) is a box whose projection on the i’th coordinate is an interval [li, ri ] with the smallest ri. Such a box C(h) exists since C(D ) is a ﬁnite set).

We let Gi (D) ∈ D be a box whose projection on the i’th coordinate is an interval [li, ri ] with the greatest li (if D is inﬁnite and no such box exists, we proceed similarly to what we did in the deﬁnition of Li (D )).

We let D = {L1 (D ), G1 (D ),..., Ld (D ), Gd (D )}. We note that D ∩ S = D ∩ S (and when D is ﬁnite, D = D ).

In both cases, (D, S ) is a solution deﬁning set for (D, S ) and the cardinality of D is at most 2d, as needed.

This Helly number is at least 2d due to Example 2.2.2.

We note that Theorem 2.4.1 implies Theorem 2.2.1 in the following way. Due to Observation 2.4.8 the Helly number in Theorem 2.2.1 is bounded from above by 2d, the Helly number in Theorem 2.4.1. Due to Example 2.2.

2 it is at least 2d, so it is 2d.

In order to avoid conﬂict in our notations, let B denote the set of boxes, let P denote the set of points for Theorem 2.4.

1, let D denote the set of demand points, and let S denote the set of supply points for the 1-center problem. For every (D, S ) ∈ 2D ×2S let r(D, S ) be the optimal radius for the 1-center problem on (D, S ), realized by making s∗ (D, S ) ∈ S a center. Looking at the set of boxes r(D, S )D = {r(D, S )di | di ∈ D } where r(D, S )di is the box with center at di and radius r(D i ), we note that s∗ (D, S ) intersects all the,S w boxes of r(D, S )D. Applying Theorem 2.4.1 on B = r(D, S )D and P = S, we take a solution deﬁning

set as determined in the proof of Theorem 2.4.1 above, and deﬁne the following variables:

–  –  –

We also deﬁne C(D, S ) ∈ S to be the optimal center. We let the range of the objective function be I + × I 2(d+1) and deﬁne the objective function to be R R ω(D, S ) = (r(D, S ), C(D, S ), l1 (D, S ), −g1 (D, S ),..., ld (D, S ), −gd (D, S )).

Clearly (D, S, ω) is a discrete abstract problem.

For every (D, S ) ∈ 2D × 2S we let F easible(D, S ) denote the set of all intersection points for the boxes r(D, S )D. From the deﬁnitions of the variables and the optimality of the solution we get Observation 9.3.5 Let D, S, W be an instance of the general discrete weighted 1-center problem in I d with R l∞ norm. For every (D, S ) ∈ 2D × 2S, F easible(D, S ) is the minimal axis-parallel box containing the 2 points (g1 (D, S ),..., gd (D, S )) and (l1 (D, S ),..., ld (D, S )), and C(D, S ) lies on its boundary.

We show now that (D, S, ω) is a (2d, 1)-dimensional DLP-type problem. (D, S, ω) obeys the Monotonicity of Demand Condition since adding a new box h to D cannot lexicographically decrease the value, i.e.

ω(D, S) ≤L ω(D ∪ {h}, S). Similarly, (D, S, ω) obeys the Monotonicity of Supply Condition since adding a new point h cannot lexicographically increase the objective function value.

Pages:     | 1 |   ...   | 14 | 15 || 17 | 18 |   ...   | 27 |

Similar works:

«FLORIDA STATE UNIVERSITY COLLEGE OF ARTS AND SCIENCES PERFORMANCE GAINS THROUGH SENSORY SYSTEMS: A DISSERTATION By FRANK SPOSARO A Dissertation submitted to the Department of Computer Science in partial fulﬁllment of the requirements for the degree of Doctor of Philosophy Degree Awarded: Spring Semester, 2015 Copyright c 2015 Frank Sposaro. All Rights Reserved. Frank Sposaro defended this dissertation on April 13, 2015. The members of the supervisory committee were: Gary Tyson Professor...»

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

«Document A: Buddhism as Destructive to Judaism Emily Sigalow and Wendy Cadge Brandeis University September 2012 Teacher Spotlight: Rabbi Avram Davis, PhD Rabbi Avram Davis, Ph.D. is the founder of Chochmat HaLev, a Jewish Renewal community in Berkeley, CA that uses meditation as one of its core practices. He received his B.A. and M.A. in Jewish Studies and Ph.D. in comparative philosophy. He is the author of two books: The Way of Flame, Judaic Mysticism, and the editor of Meditation From the...»

«REVISITING VIRTUAL MEMORY By Arkaprava Basu A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Computer Sciences) at the UNIVERSITY OF WISCONSIN-MADISON Date of final oral examination: 2nd December 2013.The dissertation is approved by the following members of the Final Oral Committee: Prof. Remzi H. Arpaci-Dusseau, Professor, Computer Sciences Prof. Mark D. Hill (Advisor), Professor, Computer Sciences Prof. Mikko H. Lipasti, Professor,...»

«EVOLUTIONARY TRADE-OFFS: EMERGENT CONSTRAINTS AND THEIR ADAPTIVE CONSEQUENCES by Bret S. Weinstein A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Biology) in The University of Michigan Doctoral Committee: Professor Emeritus Richard D. Alexander, Co-Chair Associate Professor Robyn J. Burnham, Co-Chair Professor Emeritus Gerald R. Smith Associate Professor Beverly I. Strassmann Assistant Professor Elizabeth A. Tibbetts © Bret S....»

«COMPLEXITY AND AUTONOMY IN BRONZE AGE EUROPE: ASSESSING CULTURAL DEVELOPMENTS IN EASTERN HUNGARY by Paul R. Duffy A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Anthropology) in The University of Michigan Doctoral Committee: Professor John M. O’Shea, Chair Professor Daniel G. Brown Professor Robert E. Whallon Jr. Professor Henry T. Wright © Paul R. Duffy 2010 For my Mother and Father ii ACKNOWLEDGEMENTS My interest in comparative...»

«Hydrothermal Synthesis and Characterization of Cadmium Selenide Nanocrystals by Juandria V. Williams A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Chemical Engineering) in The University of Michigan Doctoral Committee: Professor Phillip E. Savage, Chair Professor Levi T. Thompson, Jr. Associate Professor Rachel S. Goldman Associate Professor Nicholas A. Kotov © Juandria V.Williams All rights reserved To Grandma (Bernice E Lee –...»

«Relating to Work: Generation, Discourse and Social Change By Karen R. Foster A thesis submitted to the Faculty of Graduate and Postdoctoral Affairs in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Sociology Carleton University Ottawa, Ontario ©2011 Karen R. Foster Library and Archives Bibliotheque et Canada Archives Canada Published Heritage Direction du Branch Patrimoine de I'edition 395 Wellington Street 395, rue Wellington Ottawa ON K1A0N4 Ottawa ON K1A...»

«The SFRA: A Fixed Frequency FPGA Architecture by Nicholas Croyle Weaver B.A. (University of California at Berkeley) 1995 A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Computer Science in the GRADUATE DIVISION of the UNIVERSITY of CALIFORNIA at BERKELEY Committee in charge: Professor John Wawrzynek, Chair Professor John Kubiatowicz Professor Steven Brenner The dissertation of Nicholas Croyle Weaver is approved: Chair Date Date Date...»

«Disentangling the ‘talent’ concept as applied to the world of work Eva Gallardo Gallardo Aquesta tesi doctoral està subjecta a la llicència ReconeixementNoComercial – SenseObraDerivada 3.0. Espanya de Creative Commons. Esta tesis doctoral está sujeta a la licencia Reconocimiento NoComercial – SinObraDerivada 3.0. España de Creative Commons. This doctoral thesis is licensed under the Creative Commons Attribution-NonCommercialNoDerivs 3.0. Spain License. Disentangling the ‘talent’...»

«Network Like Nobody’s Watching: Demystifying Networking as a Skill for the Librarian and Information Professional Community. Leslie Howerton-Hicks B.A. MLIS Footwear Materials Librarian, Exeter Materials Center. Tracy Z. Maleeff A.A. B.A. MLIS Library Resources Manager, Duane Morris LLP. Introduction According to William W. Purkey, “You've gotta dance like there's nobody watching, love like you'll never be hurt, sing like there's nobody listening, and live like it's heaven on earth.” This...»

«THE LEVITICAL HEPTATEUCH AND PHINEHAS THE HIGH PRIEST A dissertation by YoungHye Kim Presented to The Faculty of the Graduate Theological Union in partial fulfillment of the requirements for the degree of Doctor of Philosophy Berkeley, California October, 2008 Committee Signatures Robert B. Coote, Coordinator Niek Veldhuis, Member UMI Number: 3335277 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or...»

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