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

From the last two inequalities we obtain that c2 = c2II (B 2,0 ). Hence D2II (B 2,0 ) is a solution deﬁning set for the type II 2-lpiercing problem on B 2 as well. We let

** D2II (B 2 ) = D2II (B 2,0 ).**

We note that none of the rectangles of D2II (B 2 ) is pierced by cBL. Due to Observation B.3.2, no point which lies not above and not to the right of cBL pierces any of the rectangles in D2II (B 2 ). In particularly, none of the rectangles in D2II (B 2 ) is pierced by c1, so all the rectangles in D2II (B 2 ) must be pierced by two points.

We will next deﬁne D1 (B 1 ) such that all the rectangles in D1 (B 1 ) must be pierced by one point. If bB ∈ Br 1 (this implies that the solution of the 1-piercing problem on B 1 \ Br ∪ {bB, bL } is not to the left of c1 ), we

We note that D1 (B 1 ) is a solution deﬁning set for the 1-lpiercing problem on B 1. We include BR and BT in B3 that we deﬁne below. Thus we can not decrease the solution of the type BL 3-lpiercing problem on D1 (B 1 ) ∪ D2II (B 2 ) ∪ BR ∪ BT ∪ B∗ ∪ B ∗ (for any choice of D2II (B 2 )) by decomposing it into a 1-lpiercing problem on a proper subset of D1 (B 1 ) and a 2-lpiercing problem on the remaining elements. We let B3 = B R ∪ B T, and let D3T L (B) = D1 (B 1 ) ∪ D2II (B 2 ) ∪ B3 ∪ B∗ ∪ B ∗.

From the deﬁnitions above D3T L (B) is a solution deﬁning set for the type BL 3-lpiercing problem on B.

Clearly |D3BL (B) \ (B∗ ∪ B ∗ )| ≤ (4 − 2) + (5 − 2) + (5 − 3) + (5 − 3) = 9, so |D3BL (B)| ≤ 15.

Until now, for every XX ∈ {T R, BR, T L, BL}, we have deﬁned D3XX, a solution deﬁning set for the type XX 3-lpiercing problem on B, if B is type XX 3-pierceable. It remains to handle the cases where B is not type XX 3-pierceable. In these cases the set of rectangle not pierced by cXX (i.e., B \ P (cXX )) is not 2-pierceable. By Corollary B.3.8 we take D2 (B \ P (cXX )), a solution deﬁning set for the type XX 2-lpiercing problem on B \ P (cXX ) of at most 6 rectangles. In this way D2 (B \ P (cXX )) ∪ B∗ ∪ B ∗ is not type XX 3-pierceable. We let

Due to Observation B.4.1 D3 (B) is a solution deﬁning set for the 3-lpiercing problem on B. We conclude the proof by noting that due to our cardinality calculations above we have |D3 (B)| ≤ |B∗ | + |B ∗ | + |D3T R (B) \ (B∗ ∪B ∗ )|+|D3BR (B)\(B∗ ∪B ∗ )|+|D3T L (B)\(B∗ ∪B ∗ )|+|D3BL(B)\(B∗ ∪B ∗ )| ≤ 4+2+5+6+7+10 = 34.

Bibliography [A92] N. Amenta, Finding a line transversal of axial objects in three dimensions, Proceeding of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 66-71 (1992).

[A93] N. Amenta, Helly theorems and generalized linear programming, Ph.D. dissertation, University of California at Berkeley, (1993).

[A94] N. Amenta, Helly-type theorems and generalized linear programming, Discrete Computational Geometry 12 pp. 241-261 (1994).

[AHU74] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass. (1974).

[Be83] M. Ben-Or, Lower bounds for algebraic computation trees, Proc. 15th ACM Annual Symposium on Theory of Algorithms, pp. 80-86 (1983).

[BCJLM97] A. Browne, E.M. Clarke, S. Jha, D.E. Long and W. Marrero, An improved algorithm for evaluation of ﬁxpoint expressions, Theoretical Computer Science 178(1-2), pp. 237-255 (1997).

[BFPRT73] M. Blum, R. Floyd, V. Pratt, R. Rivest and R. Tarjan, Time bounds for selection, J.

Comp. Sys. Sci. 7 pp. 448-461 (1973).

¨ [BSV03a] H. Bjorklund, S. Sandberg and Sergei Vorobyov, Randomized subexponential algorithms for parity games, Technical Report 2003-019, Department of Information Technology, Uppsala University, (2003). Available online at http://www.it.uu.se/research/reports ¨ [BSV03b] H. Bjorklund, S. Sandberg and Sergei Vorobyov, A discrete subexponential algorithm for parity games, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 2607, pp. 663-674 (2003).

¨ [BSV04] H. Bjorklund, S. Sandberg and Sergei Vorobyov, A combinatorial strongly subexponential strategy improvement algorithm for mean payoﬀ games, Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS’ 2004), Lecture Notes in Computer Science 3153, pp. 673-685, (2004).

[Chan96] T.M. Chan, Fixed-Dimensional linear programming queries made easy, Proceedings of the 12th ACM Symposium on Computational Geometry, pp. 284-290 (1996).

[Chaz87] B. Chazelle, Computing on a free tree via complexity-preserving mappings, Algorithmica 2 pp.

337-361 (1987).

[Cl86] K. L. Clarkson, Linear programming in O(n × 3d ) time, Information Processing Letters 22, pp.

21-24 (1986).

[Cl95] K. L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, J. ACM 42 (2), pp. 488-499 (1995).

[Co92] A. Condon, The complexity of Stochastic games, Information and Computation 96 pp. 203-224 (1992).

[CEIY91] M. Chrobak, D. Eppstein, G. Italiano and M. Yung, Eﬃcient sequential and parallel algorithms for computing recovery points in trees and paths, Proc. 2nd ACM SIAM Symposium on Discrete Algorithms, pp. 158-167 (1991).

[CH99] R. Cole and R. Hariharan, Dynamic LCA queries on trees, Proc. 10th ACM SIAM Symposium on Discrete Algorithms, pp. 235-244 (1999).

[CK88] M.J. Chung and M.S. Krishnamoorthy, Algorithms of placing recovery points, Information Processing Letters 28, pp. 177-181 (1988).

[CLR90] T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to algorithms, MIT Press, Cambridge (1990).

[CMNS99] F. Conti, F. Malucelli, S. Nicoloso, B. Simone, On a 2-dimensional equipartition problem, European J. Operational Research 113, pp. 215-231 (1999).

[Dant51] G. B. Dantzig, Maximization of a linear function of variables subject to linear inequalities, Activity Analysis of Production and Allocationm Koopman ed., Cowles Commission Monograph, 13, John Wiley and Sons, New York (1951).

¨ [Danz57] L. Danzer, Uber ein Problem aus der combinatorischen Geometrie, Arch. Math. (Basel) 8 pp.

344-351 (1957).

[De72] C. Derman, Finite state Markovian decision processes, Academic Press, New York (1972).

[Do73] J.P. Doignon, Convexity in cristallographical lattices, J. Geometry 3 pp. 71-85 (1973).

[Dr87] Z. Drezner, On the rectangular p-center problem, Naval Res. Logist. Quart. 34 pp. 229-234 (1987).

[Dy86] M. Dyer, On a multidimensional search technique and its application to the Euclidean one-center problem, SIAM Journal on Computing 15, pp. 725-738 (1984).

¨ [DGK63] L. Danzer, B. Grunbaum and V. Klee, Helly’s Theorem and its relatives, Proceedings of the Symposium on Pure Mathematics, 7, Convexity, American Mathematical Society, Providence, RI, pp.

101-180 (1963).

[DK90] D.P. Dobkin and D.G. Kirkpatrick, Determining the separation of preprocessed polyhedra: a uniﬁed approach Proceedings of the 17th Int. Colloq. Automata, Languages, and Programming, Lecture Notes in Computer Science 443, Springer-Verlag, pp. 400-413 (1990).

[DL79] D. Dobkin and R. Lipton, On the complexity of computations under varying set of primitives, J.

Computer and Systems Sciences 18, pp. 86-91 (1979).

[Ec93] J. Eckhoff, Helly, Radon and Carathodory type theorems, Handbook of Convex Geometry, P.M.

Gruber and J.M. Willis, eds., Elsevier Science Publishers B.V. Amsterdam (1993).

[Ed87] H. Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag, New York, Berlin, Heidelberg (1987).

[EJS93] E.A. Emerson, C.S. Jutla and A.P. Sistla, On model-checking for fragments of ν-calculus, In Costas Courcoubetis, editor, Computer Aided Veriﬁcation, 5th International Conference, CAV’93 LNCS 697 pp. 385-396, Elounda, Greece (1993).

[EW89] P. Egyed and R. Wenger, Stabbing pairwise disjoint translates in linear time, Proc. 5th ACM Symposium on Computational Geometry, pp. 364-369 (1989).

[EW91] P. Egyed and R. Wenger, Ordered stabbing of pairwise disjoint convex sets in linear time, Discrete Applied Mathematics 31 pp. 133-140 (1991).

[Fl87] R. Fletcher, Practical methods of optimization, John Wiley & Sons, New York (1987).

[Fr91] G.N. Frederickson, Optimal algorithms for tree partitioning, Proc. 2nd ACM SIAM Symposium on Discrete Algorithms, pp. 168-177 (1991).

[Fr92] G.N. Frederickson, Optimal parametric search algorithms in tress II: p-center problems and checkpointing, manuscript (1992).

[FJ83] G.N. Frederickson and D.B. Johnson, Finding k-th paths and p-centers by generating and searching good data structures, J. Algorithms 4, pp. 61-80 (1983).

[FW74] R.L. Francis and J.A. White, Facility layout and location - An analytical approach, PrenticeHall, Englewood Cliﬀs, NJ (1974).

¨ [G58] B. Grunbaum, On common transversals, Arch. Math. (Basel) 9 pp. 465-469 (1958).

[GJ79] M.R. Garey and D.S. Johnson, Computer and intractability. A guide to the theory of NPcompleteness, Freeman & Co., San Francisco (1979).

[GM96] M. Grigni and F. Manne, On the complexity of the generalized block distribution, Proc. 3rd International Workshop on Parallel Algorithms for Irregularly Structured Problems, Lecture Notes in Computer Science 1117, Springer, pp. 319-326 (1996).

[GPW93] J.E. Goodman, R. Pollack and R. Wenger, Geometric Transversal Theory, New Trends in Discrete and Computational Geometry, J. Pach, ed., Springer Verlag, Berlin, pp. 163-198, (1993).

[Hal01] N. Halman, An EGLP formulation for the simple stochastic game problem or a comment on the paper: “A subexponential randomized algorithm for the simple stochastic game problem” by W. Ludwig, Technical Report RP-SOR-01-02, Department of Statistics and Operations Research, School of Mathematical Sciences, Tel Aviv University (2001).

[Hal03] N. Halman, A Linear Time Algorithm for the Weighted Lexicographic Rectilinear 1-Center Problem in the Plane, Information Processing Letters 86, pp. 121-128, (2003).

[Hal04] N. Halman, On the power of discrete and of lexicographic Helly-type theorems, to appear in 45th IEEE Annual Symposium on Foundations of Computer Science, (2004).

[Han73] G.Y. Handler, Minimax location of a facility in an undirected tree graph, Transportation Science 7, pp. 287-293, (1973).

[Har98] S. Har-Peled, Private communication (1998).

[Hof99] M. Hoffmann, A simple linear algorithm for computing rectangular 3-centers, 11th Canadian Conference on Computational Geometry (1999).

[How60] R. A. Howard, Dynamic programming and Markov processes, M.I.T. Press, Cambridge, MA.

(1960).

[HDK64] H. Hadwiger, H. Debrunner and V. Klee, Combinatorial geometry in the plane, Rinhart and Winston, New York (1964).

[HT84] D. Harel and R.E. Tarjan, Fast algorithms for ﬁnding nearest common ancestors, SIAM J.

Computing 13, pp. 338-355 (1984).

[J98] M. Jurdzinski, Deciding the winner in parity games is in UP ∩ co-UP, Information Processing Letters 68, pp. 119-124 (2000).

[J00] M. Jurdzinski, Small progress measures for solving parity games, Lecture Notes in Computer Science 1770, pp. 290-301 (2000).

[JKP72] S.L.S. Jacoby, J.S. Kowalik and J.T. Pizzo, Iterative methods for nonlinear optimization problems, Prentice-Hall, New Jersey (1972).

[Kal92] G. Kalai, A subexponential randomized simplex algorithm, Proceedings of the 24th Annual ACM Symposium on the Theory of Computation, pp. 475-482 (1992).

[Kh79] L. G. Khachiyan, A polynomial algorithm in linear programming, Soviet Math. Dokl. 20 pp. 191Kl54] V.L. JR. Klee, Common secants for plane convex sets, Proc. Am. Math. Soc. 5, pp. 639-641 (1954).

[Ko72] E. Kohlberg, The nucleolus as a solution of a minimization problem, SIAM J. Appl. Math. 23 pp.

34-39 (1972).

[KK87] V. Klee and P. Kleinschmidt, The d-step conjecture and its relatives, Mathematics of Operations Research 12:3, pp. 719-755 (1987).

[KC92] M.T. Ko and Y.T. Ching, Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l∞ -distance, Discrete Applied Math. 40 pp. 397-410 (1992).

[KMS97] S. Khanna, S. Muthukrishnan and S. Skiena, Eﬃcient array partitioning, Proc. 24th International Colloquium on Automata, Languages and Programming, pp. 616-626 (1997).

[Le83] H. W. Lenstra Jr., Integer programming with a ﬁxed number of variables, Mathematics of Operations Research 8, pp. 538-548 (1983).

[Lu95] W. Ludwig, A subexponential randomized algorithm for the Simple Stochastic Game problem, Information and Computation 117 pp. 151-155 (1995).

[LC85] D.T. Lee and Y.T. Ching, The power of geometric duality revisited, Information Processing Letters 21 pp. 117-122 (1985).

[LW86] D.T. Lee and Y. F. Wu, Geometric complexity of some location problems, Algorithmica 1, pp.

193-211 (1986).

[Ma02] J. Matouˇek, Lectures on discrete geometry, Springer-Verlag, New York (2002).

s

[Me83b] N. Megiddo, The weighted Euclidean 1-center problem, Math. Oper. Res. 8 pp. 498-504 (1983).

[Me83c] N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms, J. ACM 30, pp. 852-865 (1983).

[Me84] N. Megiddo, Linear programming in linear time when the dimension is ﬁxed, Journal of the ACM, 31, pp. 114-27 (1984).

[Me91] N. Megiddo, Personal communication to N. Amenta (1991).

[MC90] M. Melekopoglou and A. Condon, On the complexity of the policy iteration algorithm for Stochastic games, Technical Report TR 941, University of Wisconsin (June 1990).

[MSW96] J. Matouˇek, M. Sharir and E. Welzl, A subexponential bound for linear programming, s Algorithmica 16, pp. 498-516 (1996).

[MT81] N. Megiddo and A. Tamir, An O(p2 log2 n) algorithm for the unweighted p-center problem on the line, Technical report 1981, revised in 1991. School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel (1991).

[MTZC81] N. Megiddo, A. Tamir, E. Zemel and R. Chandrasekaran, An O(n log2 n) algorithm for the k-th longest path in a tree with applications to location models, SIAM J. Computing 10, pp. 328-337 (1981).

[O97] W. Ogryczak, On the lexicographic minimax approach to location problems, European J. of Operational Research, 100 pp. 566-585 (1997).

[OM95] B. Olstad and F. Manne, Eﬃcient partitioning of sequences, IEEE Transactions on Computers 44, pp. 1322-1326 (1995).

[P95] A. Puri, Theory of hybrid systems and discrete events systems, Ph.D. dissertation, EECS, University of Berkeley (1995).

[PS85] F.P. Preparata and M.I. Shamos, Computational Geometry - An Introduction, Springer-Verlag, New York (1985).

[PV87] H.J.M. Peters and O.J. Vrieze, Surveys in game theory and related topics, CWI Tract 39, Centrum voor Wiskunde en Informatica, Amsterdam (1987).

[R72] E.M. Reingold, On the optimality of some set algorithms, J. ACM, 19 pp. 649-659 (1972).

[RRT94] S.S. Ravi, D.J. Rosenkrantz and G.K. Tayi Heuristics and special case algorithms for dispersion problems, Operations Research 42, pp. 299-310 (1994).

[Sc86] A. Schrijver, Theory of linear and integer programming, John Wiley & Sons (1986).

[Seg02] M. Segal, Lower bounds for covering problems, J. of Mathematical Modeling and Algorithms 1, pp. 17-29 (2002).

[Sei91] R. Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete Computational Geometry 6, pp. 423-434 (1991).

[Sei96] H. Seidel, Fast and Simple nested ﬁxpoints, Information Processing Letters 59, pp. 303-308 (1996).

[Sh53] L.S. Shapley, Stochastic games, Proc. of the National Academy of Sciences, U.S.A. pp. 1095-1100 (1953).

[SV88] B. Schieber and U. Vishkin, On ﬁnding lowest common ancestors: simpliﬁcation and parallelization, SIAM J. Computing 17 (6), pp. 1253-1262 (1988).

[SW92] M. Sharir and E. Welzl, A combinatorial bound for linear programming and related problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 577, pp. 569-579 (1992).

[SW96] M. Sharir and E. Welzl, Rectilinear and polygonal p-piercing and p-center problems, Proceedings of the 12th ACM Symposium on Computational Geometry, pp. 122-132 (1996).

[Ta98] A. Tamir Comments on the paper:”Heuristic and special case algorithms for dispersion problems” by S.S. Ravi, D.J. Rosenkrantz and G.K. Tayi., Operations Research 46 (1), pp. 157-158 (1998).

[Tv89] H. Tverberg, Proof of Gr¨nbaum’s conjecture on common transversals for translates, Discrete u Computational Geometry 4, pp. 191-203 (1989).

[WK88] D.W. Wang and Y.S. Kuo, A study of two geometric location problems, Information Processing Letters 28, pp. 281-286 (1988).

[ZP96] U. Zwick and M. Paterson, The complexity of mean payoﬀ games on graphs, Theoretical Computer Science 158 pp. 343-359 (1996).