An improved bound for weak epsilon-nets in the plane. (English) Zbl 07679900
MSC:
68-XX
Found 91 Documents (Results 1–91)
Stronger bounds for weak epsilon-nets in higher dimensions. (English) Zbl 07765226
Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 989-1002 (2021).
MSC:
68Qxx
A new lower bound on Hadwiger-Debrunner numbers in the plane. (English) Zbl 1481.52005
Reviewer: Mircea Balaj (Oradea)
The \(\varepsilon\)-\(t\)-net problem. (English) Zbl 07760134
Cabello, Sergio (ed.) et al., 36th international symposium on computational geometry, SoCG 2020, Zürich, Switzerland (virtual conference), June 23–26, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 164, Article 5, 15 p. (2020).
MSC:
68U05
On weak \(\epsilon\)-nets and the Radon number. (English) Zbl 1472.52002
Reviewer: Gennadiy Averkov (Magdeburg)
Random polytopes and the wet part for arbitrary probability distributions. (Polytopes aléatoires et partiesimmergées de mesures deprobabilités arbitraires.) (English. French summary) Zbl 1454.52006
Reviewer: Florian Pausinger (Belfast)
An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets. (English) Zbl 1450.52002
MSC:
52A20
When are epsilon-nets small? (English) Zbl 1435.68219
Computing optimal \(\varepsilon\)-nets is as easy as finding an unhit set. (English) Zbl 07561580
Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 87, 12 p. (2019).
On weak \(\varepsilon\)-nets and the Radon number. (English) Zbl 07559251
Barequet, Gill (ed.) et al., 35th international symposium on computational geometry, SoCG 2019, Portland, Oregon, USA, June 18–21, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 129, Article 51, 14 p. (2019).
MSC:
68U05
Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning. (English) Zbl 1433.68492
Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation. (English) Zbl 1410.68365
Diversity maximization in doubling metrics. (English) Zbl 1533.68403
Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 33, 12 p. (2018).
On a problem of Danzer. (English) Zbl 1524.52022
Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 64, 8 p. (2018).
MSC:
52C45
Further consequences of the colorful Helly hypothesis. (English) Zbl 1491.52011
Speckmann, Bettina (ed.) et al., 34th international symposium on computational geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 99, Article 59, 14 p. (2018).
MSC:
52A35
Improved deterministic algorithms for linear programming in low dimensions. (English) Zbl 1454.68171
Method for constructing optimal dark coverings. (English. Russian original) Zbl 1490.60033
Comput. Math. Math. Phys. 58, No. 7, 1040-1048 (2018); translation from Zh. Vychisl. Mat. Mat. Fiz. 58, No. 7 (2018).
Shallow packings, semialgebraic set systems, Macbeath regions, and polynomial partitioning. (English) Zbl 1433.68491
Aronov, Boris (ed.) et al., 33rd international symposium on computational geometry. SoCG 2017, Brisbane, Australia, July 4–7, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 77, Article 38, 15 p. (2017).
Using \(\epsilon\)-nets for solving the classification problem. (English) Zbl 1369.62137
Dimov, Ivan (ed.) et al., Numerical analysis and its applications. 6th international conference, NAA 2016, Lozenetz, Bulgaria, June 15–22, 2016. Revised selected papers. Cham: Springer (ISBN 978-3-319-57098-3/pbk; 978-3-319-57099-0/ebook). Lecture Notes in Computer Science 10187, 367-374 (2017).
MSC:
62H30
Positive-fraction intersection results and variations of weak epsilon-nets. (English) Zbl 1456.52009
\(\varepsilon\)-Mnets: Hitting geometric set systems with subsets. (English) Zbl 1416.52002
Reviewer: Eugenia Saorín Gómez (Bremen)
Solving \(k\)-SUM using few linear queries. (English) Zbl 1397.68093
Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 25, 17 p. (2016).
New lower bounds for \(\varepsilon\)-nets. (English) Zbl 1390.68721
Fekete, Sándor (ed.) et al., 32nd international symposium on computational geometry, SoCG’16, Boston, MA, USA, June 14–17, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-009-5). LIPIcs – Leibniz International Proceedings in Informatics 51, Article 54, 16 p. (2016).
MSC:
68U05
An algorithm to construct separable \(\epsilon\)-nets of two sets. (English. Russian original) Zbl 1359.62247
Cybern. Syst. Anal. 52, No. 6, 943-949 (2016); translation from Kibern. Sist. Anal. 2016, No. 6, 127-134 (2016).
MSC:
62H30
Solving the classification problem using \(\varepsilon\)-nets. (English. Russian original) Zbl 1349.62270
Cybern. Syst. Anal. 52, No. 4, 613-622 (2016); translation from Kibern. Sist. Anal. 2016, No. 4, 134-144 (2016).
MSC:
62H30
Killing epsilons with a dagger: a coalgebraic study of systems with algebraic label structure. (English) Zbl 1330.68194
A polynomial time approximation scheme for computing the supremum of Gaussian processes. (English) Zbl 1323.60056
Near-optimal generalisations of a theorem of Macbeath. (English) Zbl 1359.52008
Mayr, Ernst W. (ed.) et al., 31st international symposium on theoretical aspects of computer science, STACS’ 14, Lyon, France, March 5–8, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-65-1). LIPIcs – Leibniz International Proceedings in Informatics 25, 578-589 (2014).
MSC:
52A20
On coalgebras with internal moves. (English) Zbl 1445.68135
Bonsangue, M. (ed.), Coalgebraic methods in computer science. 12th IFIP WG 1.3 international workshop, CMCS 2014, colocated with ETAPS 2014, Grenoble, France, April 5–6, 2014. Revised selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 8446, 75-97 (2014).
Small strong epsilon nets. (English) Zbl 1307.65025
Reviewer: Ivana Linkeová (Praha)
MSC:
65D18
A theorem of Bárány revisited and extended. (English) Zbl 1293.52003
Proceedings of the 28th annual symposium on computational geometry, SoCG 2012, Chapel Hill, NC, USA, June 17–20, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1299-8). 333-338 (2012).
MSC:
52A20
Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension. (English) Zbl 1273.11116
Reviewer: Benjamin Doerr (Saarbrücken)
A non-linear lower bound for planar epsilon-nets. (English) Zbl 1232.68161
MSC:
68U05
A unified framework for approximating and clustering data. (English) Zbl 1288.90046
Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 569-578 (2011).
Beating the spread, time-optimal point meshing. (English) Zbl 1283.68372
Proceedings of the 27th annual symposium on computational geometry, SoCG 2011, Paris, France, June 13–15, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0682-9). 321-330 (2011).
Orphan-free anisotropic Voronoi diagrams. (English) Zbl 1228.90150
MSC:
90C48
Improved approximation for guarding simple galleries from the perimeter. (English) Zbl 1226.68122
Reviewer: Monika Nowicka (Bydgoszcz)
Relative \((p,\varepsilon )\)-approximations in geometry. (English) Zbl 1220.68106
Reviewer: Ljubiša Kocić (Niš)
Weighted geometric set cover via quasi-uniform sampling. (English) Zbl 1293.68300
Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 641-648 (2010).
A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space. (English) Zbl 1234.68441
Reprint of: Weak \(\varepsilon\)-nets have basis of size \(O(1/{\epsilon}\log (1/\epsilon))\) in any dimension. (English) Zbl 1192.68751
Polychromatic coloring for half-planes. (English) Zbl 1284.05108
Kaplan, Haim (ed.), Algorithm theory – SWAT 2010. 12th Scandinavian symposium and workshops on algorithm theory, Bergen, Norway, June 21–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13730-3/pbk). Lecture Notes in Computer Science 6139, 118-126 (2010).
PTAS for geometric hitting set problems via local search. (English) Zbl 1380.68403
Proceedings of the 25th annual symposium on computational geometry, SCG 2009, Aarhus, Denmark, June 8–10, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-501-7). 17-22 (2009).
Epsilon nets and union complexity. (English) Zbl 1380.68407
Proceedings of the 25th annual symposium on computational geometry, SCG 2009, Aarhus, Denmark, June 8–10, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-501-7). 11-16 (2009).
Topological construction of parameterized bisimulation limit. (English) Zbl 1342.68233
Chen, Y.-X. (ed.) et al., Proceedings of the fifth international symposium on domain theory (ISDT 2009), Shanghai, China, September 12–14, 2009. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 257, 55-70 (2009).
Small-size \({\varepsilon}\)-nets for axis-parallel rectangles and boxes. (English) Zbl 1304.68181
Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 639-648 (2009).
Small weak epsilon-nets. (English) Zbl 1166.52300
MSC:
52A10
Geometric set cover and hitting sets for polytopes in \({\mathbb R}^3\). (English) Zbl 1259.68210
Albers, Susanne (ed.) et al., STACS 2008. 25th international symposium on theoretical aspects of computer science, Bordeaux, France, February 21–23, 2008. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-06-4). LIPIcs – Leibniz International Proceedings in Informatics 1, 479-490, electronic only (2008).
State of the union (of geometric objects). (English) Zbl 1155.52017
Goodman, Jacob E. (ed.) et al., Surveys on discrete and computational geometry. Twenty years later. AMS-IMS-SIAM summer research conference, Snowbird, UT, USA, June 18–22, 2006. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4239-3/pbk). Contemporary Mathematics 453, 9-48 (2008).
Reviewer: Ana Pereira do Vale (Braga)
Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension. (English) Zbl 1135.68054
Random \(\varepsilon\)-nets and embeddings in \(\ell^N_\infty\). (English) Zbl 1126.46006
Reviewer: Bo’az Klartag (Princeton)
Importance sampling algorithms for Bayesian networks: principles and performance. (English) Zbl 1459.62021
New constructions of weak epsilon-nets. (English) Zbl 1375.68158
Proceedings of the 19th annual symposium on computational geometry, SCG/SoCG 2003, San Diego, CA, USA, June 8–10, 2003. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-58113-663-3). 129-135 (2003).
Guarding scenes against invasive hypercubes. (English) Zbl 1048.65025
Reviewer: Francisco Perez Acosta (La Laguna)
MSC:
65D18
A lower bound for weak \(\varepsilon\)-nets in high dimension. (English) Zbl 1015.52004
Reviewer: Johann Linhart (Salzburg)
Finite process algebras. (English) Zbl 0943.68121
Reviewer: Slaviša Prešić (VrČin)
Carathéodory’s theorem, colourful and applicable. (English) Zbl 0883.52004
Bárány, Imre (ed.) et al., Intuitive geometry. Proceedings of the 5th conference, Budapest, Hungary, September 3–8, 1995. Budapest: János Bolyai Mathematical Society. Bolyai Soc. Math. Stud. 6, 11-21 (1997).
Reviewer: H.-D.Hecker (Jena)
Eigenvalues of Laplacians on a closed Riemannian manifold and its nets. (English) Zbl 0833.58039
Reviewer: C.Bär (Freiburg)
On the divisibility of discrete sources with an additive single-letter distortion measure. (English. Russian original) Zbl 0828.94007
Probl. Inf. Transm. 30, No. 1, 27-43 (1994); translation from Probl. Peredachi Inf. 30, No. 1, 31-50 (1994).
MSC:
94A34
An upper bound for weak \(\varepsilon\)-nets of points on a circle. (English) Zbl 0834.68115
Böröczky, K. (ed.) et al., Intuitive geometry. Proceedings of the 3rd international conference held in Szeged, Hungary, from 2 to 7 September, 1991. Amsterdam: North-Holland. Colloq. Math. Soc. János Bolyai. 63, 63-66 (1994).
Reviewer: H.Brönnimann (Sophia-Antipolis)
The Helly dimension relative to a lattice. (English) Zbl 0822.52002
Böröczky, K. (ed.) et al., Intuitive geometry. Proceedings of the 3rd international conference held in Szeged, Hungary, from 2 to 7 September, 1991. Amsterdam: North-Holland. Colloq. Math. Soc. János Bolyai. 63, 11-16 (1994).
Reviewer: H.Brönnimann (Palaiseau)
Epsilon-nets and computational geometry. (English) Zbl 0801.68154
Pach, János (ed.), New trends in discrete and computational geometry. Berlin: Springer-Verlag. Algorithms Comb. 10, 69-89 (1993).
MSC:
68U05
On metric dimensions of discrete-time systems. (English) Zbl 0784.93071
Reviewer: V.Răsvan (Bucureşti)
The complexity of many cells in arrangements of planes and related problems. (English) Zbl 0691.68036
Reviewer: H.-D.Hecker
The complexity and construction of many faces in arrangements of lines and of segments. (English) Zbl 0691.68035
Reviewer: H.-D.Hecker
Approximation of Pareto set on the basis of inexact information. (English) Zbl 0602.90126
MSC:
90C31
Approximation of a Pareto set according to approximate information. (Russian) Zbl 0589.90075
Reviewer: C.Zălinescu
MSC:
90C31
Specification and verification of networks in a Petri net based language. (English) Zbl 0522.68019
Applications and theory of Petri nets, sel. Pap. 3rd Eur. Workshop, Varenna/Italy 1982, Inf.-Fachber. 66, 181-198 (1983).
An algorithm of approximate solution of systems of nonlinear equations. (English. Russian original) Zbl 0522.65039
Cybernetics 18, 228-234 (1982); translation from Kibernetika 1982, No. 2, 74-79 (1982).
Filter Results by …
Document Type
- Journal Articles (61)
- Collection Articles (30)
all
top 5
Author
- Mustafa, Nabil Hassan (16)
- Ray, Saurabh (11)
- Smorodinsky, Shakhar (7)
- Sharir, Micha (6)
- Pach, János (5)
- Rubin, Natan (5)
- Jartoux, Bruno (4)
- Matoušek, Jiří (4)
- Yuditsky, Yelena (4)
- Alon, Noga (3)
- Aronov, Boris (3)
- Bárány, Imre (3)
- Ezra, Esther E. (3)
- Ivanchuk, Maria A. (3)
- Keller, Chaya (3)
- Malyk, Igor V. (3)
- Abramova, M. V. (2)
- Brengos, Tomasz (2)
- Chan, Timothy Moon-Yew (2)
- Dutta, Kunal (2)
- Edelsbrunner, Herbert (2)
- Ghosh, Arijit (2)
- Guibas, Leonidas John (2)
- Kupavskii, Andrey (2)
- Ma, Yanfang (2)
- Martinez-Sandoval, Leonardo (2)
- Moran, Shay (2)
- Roldán-Pensado, Edgardo (2)
- Seara, Carlos (2)
- Tardos, Gábor (2)
- Varadarajan, Kasturi R. (2)
- Yehudayoff, Amir (2)
- Zhang, Min (2)
- Agarwal, Pankaj Kumar (1)
- Ashok, Pradeesha (1)
- Aurenhammer, Franz (1)
- Azmi, Umair (1)
- Babich, M. D. (1)
- Bagchi, Amitabha (1)
- Banik, Aritra (1)
- Bereg, Sergey N. (1)
- Beutelspacher, Albrecht (1)
- Bezdek, Károly (1)
- Biedl, Therese C. (1)
- Bonchi, Filippo (1)
- Bus, Norbert (1)
- Bytner, Sławomira (1)
- Cabello, Sergio (1)
- Canas, Guillermo D. (1)
- Capoyleas, Vasilis (1)
- Cardinal, Jean (1)
- Cevallos, Alfonso (1)
- Chaudhary, Amitabh (1)
- David, Haggai (1)
- de Berg, Mark Theodoor (1)
- de Carufel, Jean-Lou (1)
- Díaz-Báñez, Jose Miguel (1)
- Druzdzel, Marek J. (1)
- Eisenbrand, Friedrich (1)
- Eppstein, David Arthur (1)
- Feldman, Dan (1)
- Fradelizi, Matthieu (1)
- Fujiwara, Koji (1)
- Gambin, Barbara (1)
- Garg, Shashwat (1)
- Giannopoulos, Panos (1)
- Goaoc, Xavier (1)
- Goodrich, Michael Truman (1)
- Gordon, Yehoram (1)
- Gortler, Steven J. (1)
- Govindarajan, Sathish (1)
- Grelier, Nicolas (1)
- Har-Peled, Sariel (1)
- Hubard, Alfredo (1)
- Hurtado, Ferran (1)
- Iacono, John (1)
- Ilchi, Saeed Gh. (1)
- Kamenev, Georgy K. (1)
- Katz, Matthew J. (1)
- Kirkpatrick, David G. (1)
- Knauer, Christian (1)
- Komlós, János (1)
- Koshelev, Valery N. (1)
- Kyng, Morten (1)
- Langberg, Michael (1)
- Langerman, Stefan (1)
- Lauen, Sören (1)
- Lee, Stephanie Tien (1)
- Lin, Lin (1)
- Litvak, Aleksandr Evgen’evich (1)
- Magazinov, Alexander Nikolaevich (1)
- Maheshwari, Anil (1)
- Mehrabi, Saeed (1)
- Meka, Raghu (1)
- Mihoubi, Douadi (1)
- Milius, Stefan (1)
- Miller, Gary Lee (1)
- Miltzow, Tillmann (1)
- Montecchiani, Fabrizio (1)
- Morell, Sarah (1)
- and 31 more Authors
all
top 5
Serial
- Discrete Comput. Geom. (15)
- Comput. Geom. (10)
- J. Comb. Theory, Ser. A (2)
- SIAM J. Comput. (2)
- Theor. Comput. Sci. (2)
- Cybern. Syst. Anal. (2)
- ACM Trans. Algorithms (2)
- Discrete Math. (1)
- Inf. Process. Lett. (1)
- Isr. J. Math. (1)
- Mech. Teor. Stosow. (1)
- Probl. Inf. Transm. (1)
- Stud. Math. (1)
- Adv. Math. (1)
- J. Comput. Syst. Sci. (1)
- Monatsh. Math. (1)
- Proc. Am. Math. Soc. (1)
- Mosc. Univ. Comput. Math. Cybern. (1)
- Cybernetics (1)
- Syst. Control Lett. (1)
- J. Complexity (1)
- J. Comput. Sci. Technol. (1)
- Algorithmica (1)
- Math. Comput. Modelling (1)
- Ann. Appl. Probab. (1)
- Comput. Math. Math. Phys. (1)
- Mat. Bilt. (1)
- Vestn. Mosk. Univ., Ser. XV (1)
- J. ACM (1)
- Discrete Math. Theor. Comput. Sci. (1)
- LMS J. Comput. Math. (1)
- Log. Methods Comput. Sci. (1)
- Ann. Henri Lebesgue (1)
