More Web Proxy on the site http://driver.im/

article

Efficient randomized algorithms for some geometric optimization problems

Authors:

M. SharirAuthors Info & Claims

Discrete & Computational Geometry, Volume 16, Issue 4

Pages 317 - 337

https://doi.org/10.1007/BF02712871

Published: 01 April 1996 Publication History

Abstract

In this paper we first prove the following combinatorial bound, concerning the complexity of the vertical decomposition of the minimization diagram of trivariate functions: Let $$\mathcal{F}$$ be a collection ofn totally or partially defined algebraic trivariate functions of constant maximum degree, with the additional property that, for a given pair of functionsf, fźź $$\mathcal{F}$$, the surfacef(x, y, z)=fź(x, y, z) isxy-monotone (actually, we need a somewhat weaker property). We show that the vertical decomposition of the minimization diagram of $$\mathcal{F}$$ consists ofO(n3+ź) cells (each of constant description complexity), for any ź>0. In the second part of the paper, we present a general technique that yields faster randomized algorithms for solving a number of geometric optimization problems, including (i) computing the width of a point set in 3-space, (ii) computing the minimum-width annulus enclosing a set ofn points in the plane, and (iii) computing the "biggest stick" inside a simple polygon in the plane. Using the above result on vertical decompositions, we show that the expected running time of all three algorithms isO(n3/2+ź), for any ź>0. Our algorithm improves and simplifies previous solutions of all three problems.

References

[1]

P. Agarwal, B. Aronov, and M. Sharir, Computing lower envelopes in four dimensions with applications,Proc. 10th Annual Symp. on Computational Geometry, 1994, pp. 348---358.

Digital Library

[2]

P. Agarwal, O. Schwarzkopf, and M. Sharir, The overlay of lower envelopes in three dimensions and its applications,Proc. 11th Annual Symp. on Computational Geometry, 1995, pp. 182---189.

Digital Library

[3]

P. Agarwal, M. Sharir, and S. Toledo, New applications of parametric searching in computational geometry,J. Algorithms 17 (1994), 292---318.

Digital Library

[4]

A. Aggarwal and S. Suri, The biggest diagonal in a simple polygon,Inform. Process. Lett. 35 (1990), 13---18.

Digital Library

[5]

H. Brönnimann and B. Chazelle, Optimal slope selection via cuttings,Proc. 6th Canadian Conf. on Computational Geometry, 1994, pp. 99---103.

[6]

B. Chazelle, The polygon containment problem, in:Advances in Computing Research, Vol. I: Computational Geometry (F. Preparata, ed.), JAI Press, Greenwich, CT, 1993, pp. 1---33.

[7]

B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications,Proc. 16th Internat. Colloq. on Automata, Languages and Programming, 1989, pp. 179---192. Lecture Notes in Computer Science, Vol. 371, Springer-Verlag, Berlin. (Also inTheoret. Comput. Sci. 84 (1991), 77---105.)

Digital Library

[8]

B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Diameter, width, closest line pair, and parametric searching,Discrete Comput. Geom. 10 (1993), 183---196.

Digital Library

[9]

B. Chazelle and M. Sharir, An algorithm for generalized point location and its applications,J. Symbolic Comput. 10 (1990), 281---309.

Digital Library

[10]

K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres,Discrete Comput. Geom. 5 (1990), 99---160.

Digital Library

[11]

K. Clarkson and P. Shor, Applications of random sampling in computational geometry, II,Discrete Comput. Geom. 4 (1989), 387---421.

Digital Library

[12]

M. de Berg, K. Dobrindt, and O. Schwarzkopf, On lazy randomized incremental construction,Discrete Comput. Geom. 14 (1995), 261---286.

Digital Library

[13]

M. de Berg, D. Halperin, and L. Guibas, Vertical decomposition for triangles in 3-space,Proc. 10th Annual Symp. on Computational Geometry, 1994, pp. 1---10.

Digital Library

[14]

M. Dillencourt, D. Mount, and N. Netanyahu, A randomized algorithm for slope selection,Internat. J. Comput. Geom. Appl. 2 (1992), 1---27.

[15]

H. Ebara, N. Fukuyama, H. Nakano, and Y. Nakanishi, Roundness algorithms using the Voronoi diagrams,First Canadian Conf. on Computational Geometry, 1989.

[16]

A. Forbes, Generalized regression problems in metrology,Numer. Algorithms 5 (1993), 523---533.

[17]

D. Halperin and M. Sharir, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains,Discrete Comput. Geom. 12 (1994), 313---326.

Digital Library

[18]

D. Haussler and E. Welzl, ¿-nets and simplex range queries,Discrete Comput. Geom. 2 (1987), 127---151.

Digital Library

[19]

M. Houle and G. Toussaint, Computing the width of a set,IEEE Trans. Pattern Anal. Mach. Intell. 5 (1988), 761---765.

Digital Library

[20]

M. Katz and M. Sharir, Optimal slope selection via expanders,Inform. Process. Lett. 47 (1993), 115---122.

Digital Library

[21]

M. Katz and M. Sharir, An expander-based approach to geometric optimization,Proc. 9th Annual Symp. on Computational Geometry, 1993, pp. 198---207. (Also to appear inSIAM J. Comput.)

Digital Library

[22]

V. B. Le and D. T. Lee, Out-of-roundness problem revisited,IEEE Trans. Pattern Anal. Mach. Intell. 13 (1991), 217---223.

Digital Library

[23]

E. H. Lockwood,A Book of Curves, Cambridge University Press, Cambridge, 1967.

[24]

J. Matoušek, Randomized optimal algorithm for slope selection,Inform. Process. Lett. 39 (1991), 183---187.

Digital Library

[25]

M. McKenna, The biggest stick problem,First Computational Geometry Day, New York University, New York, 1986.

[26]

N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms,J. Assoc. Comput. Mach. 30 (1983), 852---865.

Digital Library

[27]

N. Megiddo, Linear programming in linear time when the dimension is fixed,J. Assoc. Comput. Mach. 31 (1984), 114---127.

Digital Library

[28]

M. Pellegrini, On collision-free placement of simplices and the closest pair of lines in 3-space,SIAM J. Comput. 23 (1994), 133---153.

Digital Library

[29]

M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions,Discrete Comput. Geom. 12 (1994), 327---345.

Digital Library

[30]

M. Sharir and P. Agarwal,Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, Cambridge, 1995.

Digital Library

[31]

M. Smid and R. Janardan, On the Width and Roundness of a Set of Points in the Plane, Tech. Rept. MPI-I-94-111, Max-Planck-Institut für Informatik, Saarbrücken, 1994.

[32]

K. Swanson, An optimal algorithm for roundness determination on convex polygons,Proc. 3rd Workshop on Algorithms Data Structures, 1993, pp. 601---609.

Digital Library

[33]

E. Welzl, Constructing the visibility graph forn line segments inO(n2) time,Inform. Process. Letters 20, 167---171.

[34]

G. Wilfong, private communication.

Cited By

Ahn TChung CAhn HBae SCheong OYoon S(2024)Minimum-Width Double-Slabs and Widest Empty Slabs in High DimensionsLATIN 2024: Theoretical Informatics10.1007/978-3-031-55598-5_20(303-317)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-55598-5_20
Aronov BFiltser OKatz MSheikhan K(2022)Bipartite Diameter and Other Measures Under TranslationDiscrete & Computational Geometry10.1007/s00454-022-00433-568:3(647-663)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00454-022-00433-5
Chanchary FMaheshwari ASmid M(2021)Window queries for intersecting objects, maximal points and approximations using coresetsDiscrete Applied Mathematics10.1016/j.dam.2021.03.009305:C(295-310)Online publication date: 31-Dec-2021
https://dl.acm.org/doi/10.1016/j.dam.2021.03.009
Show More Cited By

Efficient randomized algorithms for some geometric optimization problems

Recommendations

Efficient Geometric Algorithms on the EREW PRAM

We present a technique that can be used to obtain efficient parallel geometric algorithms in the EREW PRAM computational model. This technique enables us to solve optimally a number of geometric problems in O(log n) time using O(n/log n) EREW PRAM ...
Simple randomized algorithms for closest pair problems

We present a conceptually simple, randomized incremental algorithm for finding the closest pair in a set of n points in D-dimensional space, where D ≥ 2 is a fixed constant. Much of the work reduces to maintaining a dynamic dictionary. Using dynamic ...
Efficient algorithms for geometric pattern matching

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete & Computational Geometry

Discrete & Computational Geometry Volume 16, Issue 4

April 1996

160 pages

ISSN:0179-5376

Issue’s Table of Contents

Copyright © Copyright © 1996 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 1996

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ahn TChung CAhn HBae SCheong OYoon S(2024)Minimum-Width Double-Slabs and Widest Empty Slabs in High DimensionsLATIN 2024: Theoretical Informatics10.1007/978-3-031-55598-5_20(303-317)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-55598-5_20
Aronov BFiltser OKatz MSheikhan K(2022)Bipartite Diameter and Other Measures Under TranslationDiscrete & Computational Geometry10.1007/s00454-022-00433-568:3(647-663)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00454-022-00433-5
Chanchary FMaheshwari ASmid M(2021)Window queries for intersecting objects, maximal points and approximations using coresetsDiscrete Applied Mathematics10.1016/j.dam.2021.03.009305:C(295-310)Online publication date: 31-Dec-2021
https://dl.acm.org/doi/10.1016/j.dam.2021.03.009
Schöpfer FChernov A(2020)Certified Efficient Global Roundness EvaluationJournal of Optimization Theory and Applications10.1007/s10957-020-01689-8186:1(169-190)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s10957-020-01689-8
Cabello SCibulka JKynčl JSaumell MValtr PCheng SDevillers O(2014)Peeling Potatoes Near-Optimally in Near-Linear TimeProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582159(224-231)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582159
Mukherjee JMahapatra PKarmakar ADas S(2011)Minimum width rectangular annulusProceedings of the 5th joint international frontiers in algorithmics, and 7th international conference on Algorithmic aspects in information and management10.5555/2021911.2021951(364-374)Online publication date: 28-May-2011
https://dl.acm.org/doi/10.5555/2021911.2021951
Chan T(2009)Dynamic CoresetsDiscrete & Computational Geometry10.5555/3116272.311651442:3(469-488)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.5555/3116272.3116514
Chan TTeillaud M(2008)Dynamic coresetsProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377680(1-9)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1377676.1377680
Agarwal PProcopiuc CVaradarajan K(2005)Approximation Algorithms for a k-Line CenterAlgorithmica10.1007/s00453-005-1166-x42:3-4(221-230)Online publication date: 1-Jul-2005
https://dl.acm.org/doi/10.1007/s00453-005-1166-x
Koltun V(2004)Almost tight upper bounds for vertical decompositions in four dimensionsJournal of the ACM10.1145/1017460.101746151:5(699-730)Online publication date: 1-Sep-2004
https://dl.acm.org/doi/10.1145/1017460.1017461
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents