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

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 15 | 16 || 18 | 19 |   ...   | 27 |

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

-- [ Page 17 ] --

We now show that (D, S, ω) obeys both Locality Conditions and that it obeys the Violation Condition. Let (D, S ) ∈ 2D ×2S and (D, S ) ∈ 2D ×2S be such that ω(D, S ) =L ω(D, S ) (so due to Observation 9.3.5 F easable(D, S ) = F easable(D, S )). We need to show that the following two properties hold. ∀h ∈ D, ω(D ∪ {h}, S ) L ω(D, S ) if and only if ω(D ∪ {h}, S ) L ω(D, S ), and ∀h ∈ S, ω(D, S ∪ {h}) L ω(D, S ) if and only if ω(D, S ∪ {h}) L ω(D, S ).

Regarding the second property we note (for every set X ∈ I d, let Int(X) denote its interior and let ∂(X) R denote its boundary)

–  –  –

Case 1 occurs if and only if r(D, S )di does not intersect F easible(D, S ) ∩ S. This happens if and only if r(D, S )di does not intersect F easible(D, S ) ∩ S, which occurs if and only if r(D ∪ {di }, S ) r(D, S ).

Case 2 occurs if and only if C(D, S ) ∈ r(D, S )di and r(D, S )di ∩ F easible(D, S ) ∩ S = ∅. This / happens if and only if C(D, S ) ∈ r(D, S )di and r(D, S )di ∩ F easible(D, S ) ∩ S = ∅, which occurs if / and only if r(D ∪ {di }, S ) = r(D, S ) and C(D ∪ {di }, S ) L C(D, S ).

Case 3 occurs if and only C(D, S ) ∈ r(D, S )di, and there exists j such that among the projections of the boxes in r(D, S )D ∪ {r(D, S )di } on the j’th coordinate, the projection of r(D, S )di results an interval [l, r] with either the smallest r or greatest l. This happens if and only if C(D, S ) ∈ r(D, S )di, and among the projections of the boxes in r(D, S )D ∪ {r(D, S )di } on the j’th coordinate, the projection of r(D, S )di results an interval [l, r] with either the smallest r or greatest l. This occurs if and only if r(D ∪{di }, S ) = r(D, S ), C(D ∪{di }, S ) =L C(D, S ), and (l1 (D ∪{di }, S ), −g1 (D ∪{di }, S ),..., ld (D ∪ {di }, S ), −gd (D ∪ {di }, S )) L (l1 (D, S ), −g1 (D, S ),..., ld (D, S ), −gd (D, S ).

We have just proved that ∀h ∈ D, ω(D ∪ {h}, S ) L ω(D, S ) if and only if ω(D ∪ {h}, S ) L ω(D, S ). Hence (D, S, ω) is a discrete LP-type problem which satisﬁes the Violation Condition.

It is easy to verify that B(D, S) = ({L1 (D, S), G1 (D, S),..., Ld (D, S), Gd (D, S)}, {C(D, S)}) is a basis of a feasible and bounded (D, S) and that the problem is of d-dimension 2d and s-dimension 1.

The “violation test” can easily be implemented in constant time. For a basis B = (BD, BS ) and a delement di, ω(BD ∪{di }, BS ) ω(B) if and only if either r(B)di does not contain C(B), or there exists j such that among the projections of the boxes in r(B)D ∪{r(B)di } on the j’th coordinate, the projection of r(B)h results an interval [l, r] with either the smallest r or greatest l. For an s-element h, ω(BD, BS ∪ {h}) ω(B) if and only if either h lies in the interior of F easible(B), or h lies on the boundary of F easible(B) and h ≤L C(B). The “basis calculation” can be implemented in constant time by calling the violation test a constant number of times. Using a DLP-algorithm such as the one stated in Section 6.3.3, we conclude with

–  –  –

9.3.4 Discrete planar rectilinear p-center problem (p 1) Lemma 9.3.

7 The d-Helly number of the Helly theorem corresponding to the discrete planar rectilinear 2-center problem is unbounded for p 1.

Proof: The fact that the discrete planar rectilinear p-center problem (p 1) does not have a ﬁnite d-Helly number can be proved similarly to the proof of Lemma 9.2.4. Instead of constructing a circle of perimeter (2k + 1)p + 1, we construct a square of perimeter (2k + 1)p + 1 (in l∞ norm) whose sides are rotated by Π radians relatively to the axes.

Corollary 9.3.8 The discrete planar rectilinear 2-center problem cannot be formulated as a ﬁxed d-dimensional discrete LP-type problem.

We conclude this subsection with giving a lower bound for this problem.

Lemma 9.3.

9 ([Seg02]) The discrete planar rectilinear 2-center problem requires Ω(n log n) time under the algebraic computation tree model.

9.4 Euclidean p-center problems The deﬁnition is analogous to the one of the planar rectilinear p-center problem where the metric is Euclidean.

9.4.1 Continuous Euclidean p-center problems Megiddo [Me83a] gives a deterministic linear time solution algorithm for the planar Euclidean 1-center problem. [SW92] formulate the Euclidean 1-center problem in I d as a (d + 1)-dimensional LP-type problem R and thus solve it in randomized linear time. The Helly theorem corresponding to this problem with λ = 1 is just the Radius theorem (Theorem 2.1.1).

We conclude this subsection with giving a lower bound for this problem.

Lemma 9.4.

1 ([Seg02]) The Euclidean planar 2-center problem requires Ω(n log n) time under the algebraic computation tree model.

9.4.2 Discrete planar Euclidean 1-center problem Lee and Wu prove Lemma 9.4.

2 ([LW86]) The discrete planar Euclidean 1-center requires Ω(n log n) time under the decision tree computation model ([AHU74]).

[LW86] solve this problem in Θ(n log n) optimal time. The Helly theorem corresponding to this problem with λ = 1 is the discrete Radius Theorem, which has unbounded Helly number (Corollary 2.2.5).

Lemma 9.4.

3 The d-Helly number of the Helly theorem corresponding to the discrete planar Euclidean 1-center problem is unbounded.

9.5 A summary of Helly numbers for p-center problems in diﬀerent spaces We give a summary of the Helly numbers and d-Helly numbers of the Helly theorems corresponding to the various p-center problems.

–  –  –

All results marked by † are due to [DG82]. The result marked by ‡ is due to Helly’s Theorem.

Regarding the s-Helly numbers of the various discrete p-center problems we have Observation 9.5.1 The s-Helly number of the Helly theorem corresponding to any p-center problem is p.

This is true because the optimal solution has a radius length of at least r if and only if locating the centers at any p locations will yield a radius which is not smaller than r. In other words, for every real r we have ∀S with |S | ≤ p, rp (D, S ) ≥ r ⇒ rp (D, S) ≥ r.

We note that due to Corollary 4.1.3 (Corollary 4.2.3) every p-center (discrete p-center) problem which has an unbounded Helly (d-Helly) number cannot be formulated as a ﬁxed-dimensional LP-type (discrete LP-type) problem, respectively.

Chapter 10 Line transversals in the plane In this section we deal with various planar line transversal problems. In a line transversal decision problem we are given a set of objects H and need to decide whether H admits a line transversal (i.e., a line which has a non-empty intersection with each object in H). In a line transversal optimization problem we have to ﬁnd the minimal scaling factor λ∗ ∈ I + such that there exists a line which has a non-empty intersection R with each scaled object in H. We note that the unscaled family of objects admits a line transversal if and only if the optimal scaling factor λ∗ is at most 1.

The various line transversal problems diﬀer in the restrictions given on the objects in H and on the possible choices of the line transversals.

10.1 Continuous case A possible restriction on the objects in H is that they are translates of a convex set O containing the origin.

We refer to the origin as its reference point. h is a translate of O if there exists a translation vector c ∈ I 2 R + such that h = O + c = {x + c | x ∈ O}. For every scaling factor λ ∈ I R and translate h = O + c let λh = λO + c be the scaled translate (i.e., homothet) of O, which results from scaling O by factor of λ relatively to its reference point, while keeping the translation vector c ﬁxed.

In the line transversal of translates (decision) problem we are given a convex set O containing the origin as its reference point, and a set C = {c1,..., cn } of translation vectors, such that the objects in H = {O + ci ; i = 1,..., n}, are pairwise disjoint. Tverberg [Tv89] showed that if every family H ⊆ H with |H | ≤ 5 admits a line transversal, then also H admits a line transversal (Theorem 2.1.8(v)). Egyed and Wenger [EW89] use this theorem to give a deterministic linear time algorithm to ﬁnd such a line transversal.

Amenta [A94] solves the corresponding optimization problem in randomized linear time. She ﬁrst uses Tverberg’s theorem to formulate the problem as a parameterized Helly system. She then assumes that the set of translates is in general position, to get that the corresponding mathematical programming problem meets the Unique Minimum Condition. Then she applies her main theorem, Theorem 5.1.4, to get a ﬁxeddimensional LP-type formulation for this problem. Last, she applies the randomized LP-type algorithms to solve the problem in linear time. We comment that if the lexicographic version of Tverberg’s theorem has a ﬁnite Helly number (see Theorems 2.3.7, 2.3.8 and 2.3.9 for examples of lexicographic versions of Helly theorems about line transversals), then it will be possible to solve the problem (in the same time complexity) without assuming general position, by using Theorem 5.3.6.

For motivation purposes Amenta notes that the line transversal at λ∗ is tangent to at most three translates, for any non-degenerate example. Since the corresponding Helly number is 5, it is easy to construct situations in which the line transversal is tangent to exactly three of the ﬁve translates. Let us look at the example given by [A93] (Figure 10.1).

–  –  –

Consider the line transversals of the three central balls, as they grow while we increase the scaling factor λ. Assuming that the balls are in general position, there will be three distinct moments (w.r.t. the scaling factor) at which a new connected subset of line transversals becomes feasible. The two remaining balls are positioned so that only the last of these subsets contains a transversal of the whole family.

When the set O is a unit circle this optimization problem is equivalent to both the Euclidean 1-line center problem and the set width problem applied on the set C of translation vectors. (In the Euclidean 1-line center we are given a family H of points and ﬁnd a line which minimizes the maximal distance r of a point in H to the line. In the set width problem we have the same input and want to ﬁnd a pair of closest parallel lines between which all the points in H lie. We note that the line which is parallel to these two lines and lies at equal distance from them, is a line center of H). Both problems have a lower bound of Ω(n log n) under the algebraic computation tree model ([LW86]).

A similar problem is the line transversal of axis-parallel rectangles. Here the family H of objects is of (not necessarily pairwise disjoint) axis-parallel rectangles. The decision problem is solved in linear time via LP-type algorithms or by reducing it to linear programming ([A92], [A94], [Me91]). We are unaware of any linear time algorithms for the corresponding optimization problem. We note that the optimization problem is solvable in randomized linear time by a similar way to the solution of the line transversal of translates optimization problem (for this we use either Theorem 2.3.8 and Theorem 5.3.6, or Theorems 2.1.5, 2.3.8 and 5.3.7).

The last problem we consider in this chapter is the line transversal of a totally separable set H of convex sets (see Deﬁnition 2.1.3). We are unaware of any linear time algorithms for the decision problem, even when the convex sets in H are simple. We call the objects in H simple if they have a constant size storage description, and if the intersections and common tangents between any two objects can be found in constant time. If in addition to the objects in H, we are given an order in which a line transversal should meet the sets, the algorithm of Egyed and Wenger [EW91] solves the problem in linear time. We note in passing that if we are not given this order, it is possible to solve the optimization problem in randomized linear time in a similar way to the solution of the line transversal of translates optimization problem (by using either Theorem 2.3.

7 and Theorem 5.3.6, or Theorems 2.1.4, 2.3.7 and 5.3.7). As explained above, the solution of the optimization problem implies the solution of the corresponding decision problem.

We refer to all the problems in this subsection as continuous because the line transversal can be in any direction and can intersect the y-axis at any point.

10.2 Discrete case I - A ﬁnite number of allowed directions of line transversals In this subsection we deﬁne a discrete version for the line transversal of axis-parallel rectangles optimization problem. We solve it in randomized linear time by using the discrete LP-type framework.

Problem 10.2.1 Given are a set D = {d1,..., dn } of (not necessarily pairwise disjoint) axis-parallel compact rectangles, and a set S = {s1,..., sm } of allowed line directions. Find the minimal scaling factor λ∗ = 1 λ1 (D, S) ∈ I +, such that λ∗ D admits a line transversal whose direction is in S.

R 1 If we choose S to be the (inﬁnite) set of all possible directions, this problem coincides with the continuous one. We can assume that S does not contain the vertical direction and that the directions in S are such that the allowed lines are {y = ax + b | a ∈ S}. (If S does contain a vertical direction, we will take the minimal solution (i.e., scaling factor) of Problem 10.2.1 on S without the vertical direction and on the vertical direction alone. We solve the latter problem in linear time by solving the weighted 1-center problem on the line. The input set of points for this problem is {p1,..., pn }, where for all i, pi is the projection of the reference point of rectangle di on the x-axis. The weight ωi associated to each point pi is l1, where li i is the length of the projection of rectangle di on the x-axis (see Chapter 9 for the deﬁnition of the weighted 1-center problem)).

Pages:     | 1 |   ...   | 15 | 16 || 18 | 19 |   ...   | 27 |

Similar works:

«Volume 1 Performance Based Regulations: The Viability of the Modelling Approach as a Methodology for Building Energy Compliance Demonstration Rokia Mohamed Saad Raslan Department of Environmental Design and Engineering The Bartlett School of Graduate Studies University College London A Thesis Submitted for the Degree of Doctor of Philosophy University College London University of London Student Declaration The author of this thesis, Miss Rokia Raslan, confirms that the work presented in this...»

«Model building and SUSY breaking on D-branes Dmitry Malyshev 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 physics Adviser: Herman Verlinde September 2008 c Copyright by Dmitry Malyshev, 2008. All rights reserved. Abstract In the recent years there has been an increase of the interest in applying the String theory to construct viable extensions of the Standard Model and to ﬁnd...»

«SCALING AND PATTERN FORMATION IN CONDENSED MATTER SYSTEMS BY PAK YUEN CHAN B.S., The Chinese University of Hong Kong, 2003 DISSERTATION Submitted in partial fulﬁllment of the requirements for the degree of Doctor of Philosophy in Physics in the Graduate College of the University of Illinois at Urbana-Champaign, 2007 Urbana, Illinois c 2007 by Pak Yuen Chan. All rights reserved. Abstract In this dissertation, I present analytical and numerical work regarding the scaling behavior of three...»

«DEVELOPMENT OF INTEGRATED SEMICONDUCTOR OPTICAL SENSORS FOR FUNCTIONAL BRAIN IMAGING A DISSERTATION SUBMITTED TO THE DEPARTMENT OF ELECTRICAL ENGINEERING AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Thomas T. Lee August 2008 c Copyright by Thomas T. Lee 2008 All Rights Reserved ii Abstract Optical imaging of neural activity is a widely accepted technique for imaging brain function in the ﬁeld of...»

«SELF-ASSEMBLED PEPTIDE TEMPLATE DIRECTED SYNTHESIS OF ONE-DIMENSIONAL INORGANIC NANOSTRUCTURES and THEIR APPLICATIONS A DISSERTATION SUBMITTED TO MATERIALS SCIENCE AND NANOTECHNOLOGY PROGRAM OF THE GRADUATE SCHOOL OF ENGINEERING AND SCIENCE OF BILKENT UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY by HANDAN ACAR December, 2012 ii I certify that I have read this thesis and that in my opinion it is fully fully adquate, in scope and quality, as a...»

«BERICHTE UND DISKUSSIONEN Neue Forschungen zum Neuplatonismus (1995 – 2003). Teil I Carlos Steel und Christoph Helmig, Leuven Daß das Interesse und damit auch die Arbeit zur spätantiken Philosophie und speziell zum Neuplatonismus in den letzten Jahren rasch angewachsen ist, zeigt schon ein Blick auf die zahlreichen Publikationen und die steigende Anzahl von Konferenzen und Forschungsprojekten, die sich diesem Themenkreis widmen. Der folgende Artikel soll einen Überblick geben über die...»

«The packaging of 7SL RNA by 1 by Sarah Elizabeth Keene A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Microbiology and Immunology) in the University of Michigan 2012 Dissertation committee: Associate Professor Alice Telesnitsky, Chair Professor Kathy Spindler Professor Nils G. Walter Associate Professor David J. Miller Assistant Professor Akira Ono © Sarah Elizabeth Keene All rights reserved. Acknowledgments I am grateful to my...»

«Translation Validation of Optimizing Compilers by Yi Fang A dissertation submitted in partial fulﬁllment of the requirements for the degree of Doctor of Philosophy Department of Computer Science Courant Institute of Mathematical Sciences New York University December, 2005 Advisor: Amir Pnueli Abstract There is a growing awareness, both in industry and academia, of the crucial role of formally verifying the translation from high-level source-code into lowlevel object code that is typically...»

«IV: COLONIALISM AND REVOLUTION: FANON MEETS BOURDIEU But above all I wanted to get away from speculation – at that time [1960s], the works of Frantz Fanon, especially The Wretched of the Earth, were the latest fashion, and they struck me as being false and dangerous. Pierre Bourdieu, Interview, “Fieldwork in Philosophy” (1990 [1986]: 7) What Fanon says corresponds to nothing. It is even dangerous to make the Algerians believe the things he says. This would bring them to a utopia. And I...»

«37? Mo, 36 Va BURNOUT AMONG NURSING FACULTY IN TEXAS DISSERTATION Presented to the Graduate Council of the University of North Texas in Partial Fulfillment of the Requirements For the Degree of DOCTOR OF PHILOSOPHY By Nanci Terese Thomas, M.S., R.N. Denton, Texas August, 1992 37? Mo, 36 Va BURNOUT AMONG NURSING FACULTY IN TEXAS DISSERTATION Presented to the Graduate Council of the University of North Texas in Partial Fulfillment of the Requirements For the Degree of DOCTOR OF PHILOSOPHY By...»

«HOUSING INTERVENTIONS AND ITS INFLUENCE ON URBAN DEVELOPMENT: Opportunities and Challenges in Mixed Informal Settlements, in Dar es Salaam Tanzania Dissertation to conferral of the academic degree Doctor of Philosophy at the Faculty of Architecture of Bauhaus University Weimar Submitted by Shubira Kalugila Date of birth 28.06.1974 Weimar, 2013 Reviewers Professor Dr. Frank Eckardt Professor Dr. Wilbard Kombe Date of disputation 19.03.2014 i DECLARATION OF HONOUR I hereby declare that I have...»

«Electrohydrodynamic Patterning of Functional Materials Pola Goldberg Oppenheimer A Dissertation Submitted for the Degree of Doctor of Philosophy July 2011 Supervisor Prof. Dr. Ullrich Steiner University of Cambridge Cavendish Laboratories Department of Physics Churchill College To the three most precious women in my life and heart: My daughter-Roni My mother-Luda My late grandmother-Bathia Declaration This dissertation is the result of my own work and includes nothing which is the outcome of...»

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