×

Construction of \(\epsilon\)-nets. (English) Zbl 0701.68040

Summary: Let S be a set of n points in the plane and let \(\epsilon\) be a real number, \(0<\epsilon <1\). We give a deterministic algorithm, which in time \(0(n\epsilon^{-2}\log (1/\epsilon)+\epsilon^{-8})\) (resp. \(0(n\epsilon^{-2}\log (1/\epsilon)+\epsilon^{-10})\) constructs an \(\epsilon\)-net \(N\subset S\) of size \(0((1/\epsilon)(\log (1/\epsilon))^ 2)\) for intersections of S with double wedges (resp. triangles); this means that any double wedge (resp. triangle) containing more than \(\epsilon n\) points of S contains a point of N. This gives \(0(n \log n)\) deterministic preprocessing for the simplex range-counting algorithm of D. Haussler and E. Welzl [Discrete Comput. Geom. 2, 127-151 (1987; Zbl 0619.68056)] (in the plane).
We also prove that given a set L of n lines in the plane, we can cut the plane into \(0(\epsilon^{-2})\) triangles in such a way that no triangle is intersected by more than \(\epsilon\) n lines of L. We give a deterministic algorithm for this with running time \(O(n\epsilon^{- 2}\log (1/\epsilon))\). This has numerous applications in various computational geometry problems.

MSC:

68W10 Parallel algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Citations:

Zbl 0619.68056
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] P. K. Agarwal: A deterministic algorithm for partitioning arrangements of lines and its applications,Proc. 5th Ann. ACM Symposium on Computational Geometry (1989), pp. 11-21 (full version to apear inDiscrete Comput. Geom.).
[2] P. K. Agarwal: Ray shooting and other applications of spanning trees with low stabbing number,Proc. 5th Ann. ACM Symposium on Computational Geometry (1989), pp. 315-325 (full version to appear inDiscrete Comput. Geom.).
[3] M. Ajtai, J. Komlós, E. Szemerédi: AnO(n logn) sorting network,Proc. 15th ACM Symp. on Theory on Computing (1983), pp. 1-9. · Zbl 0523.68048
[4] B. Chazelle, J. Friedman: A deterministic view of random sampling and its use in geometry, Report CS-TR-181-88 (extended abstract inProc. 29th Ann. IEEE Symposium on Foundations of Computer Science (1988), pp. 539-549).
[5] B. Chazelle, E. Welzl: Quasi-optimal range searching in spaces of finite VC-dimension,Discrete Comput. Geom.4 (1989), 467-490. · Zbl 0681.68081 · doi:10.1007/BF02187743
[6] V. Chvátal: A greedy heuristics for the set-covering problem,Math. Oper. Res.4 (1979), 233-235. · Zbl 0443.90066 · doi:10.1287/moor.4.3.233
[7] K. Clarkson, P. Shor: Applications of random sampling in computational geometry, II,Discrete Comput. Geom.4 (1989), 387-421. · Zbl 0681.68060 · doi:10.1007/BF02187740
[8] K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl: Combinatorial complexity for arrangements of curves and surfaces,Proc. 29th Ann. IEEE Symposium on Foundations of Computer Science (1988), pp. 568-579.
[9] R. Cole: Slowing down sorting networks to obtain faster sorting algorithms,J. Assoc. Comput. Mach.31 (1984), 200-208. · Zbl 1378.68037
[10] R. Cole, J. Salowe, W. L. Steiger, E. Szemerédi: An optimal-time algorithm for slope selection,SIAM J. Comput.18 (1989), 792-810. · Zbl 0678.68033 · doi:10.1137/0218055
[11] H. Edelsbrunner:Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[12] H. Edelsbrunner, L. Guibas, J. Herschberger, R. Seidel, M. Sharir, J. Snoeyink, E. Welzl: Implicitly representing arrangements of lines or segments,Discrete Comput. Geom.4 (1989), 433-466. · Zbl 0688.68031 · doi:10.1007/BF02187742
[13] H. Edelsbrunner, E. Welzl: Constructing belts in 2-dimensional arrangements,SIAM J. Comput.15 (1986), 271-284. · Zbl 0613.68043 · doi:10.1137/0215019
[14] M. R. Garey, D. S. Johnson;Computers and Intractability, Freeman, San Francisco, 1979. · Zbl 0411.68039
[15] D. Haussler, E. Welzl:ɛ-nets and simplex range queries,Discrete Comput. Geom.2 (1987), 127-151. · Zbl 0619.68056 · doi:10.1007/BF02187876
[16] L. Lovász: On the ratio of optimal integral and fractional cover,Discrete Math.13 (1975), 383-390. · Zbl 0323.05127 · doi:10.1016/0012-365X(75)90058-8
[17] J. Matoušek:Approximate Halfplanar Range Counting, KAM Series 59-87, Charles University, Prague, 1987.
[18] J. Matoušek: Cutting hyperplane arrangements, 6th ACM Symposium on Computational Geometry, 1990. · Zbl 0765.68210
[19] J. Matoušek: Spanning trees with low crossing number, to appear inInform. Theoret. Applic.
[20] N. Megiddo: Applying parallel computation algorithm in the design of serial algorithms,J. Assoc. Comput. Mach.30 (1983), 852-865. · Zbl 0627.68034 · doi:10.1145/2157.322410
[21] J. Pach, W. Steiger, E. Szemerédi: An upper bound for the number of planark-sets,Proc. 30th Ann. IEEE Symposium on Foundations of Computer Science (1989), pp. 72-81.
[22] S. Suri: A linear algorithm for minimum link paths inside a simple polygon,Comput. Vision Graphics Image Process.35 (1986), 99-110. · Zbl 0624.68101 · doi:10.1016/0734-189X(86)90127-1
[23] V. N. Vapnik, A. Ya. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities,Theory Probab. Appl.16 (1971), 264-280. · Zbl 0247.60005 · doi:10.1137/1116025
[24] E. Welzl: Partition trees for triangle counting and other range searching problems,Proc. 4th ACM Symposium on Computational Geometry (1988), pp. 23-33.
[25] E. Welzl: More onk-sets of finite sets in the plane,Discrete Comput. Geom.1 (1986), 95-100. · Zbl 0598.52007 · doi:10.1007/BF02187686
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.