---
OA_type: closed access
_id: '2423'
abstract:
- lang: eng
text: A finite set N ⊃ Rd is a weak ε-net for an n-point set X ⊃ Rd (with respect
to convex sets) if N intersects every convex set K with |K ∩ X| ≥ εn. We give
an alternative, and arguably simpler, proof of the fact, first shown by Chazelle
et al. [7], that every point set X in Rd admits a weak ε-net of cardinality O(ε-d
polylog(1/ε)). Moreover, for a number of special point sets (e.g., for points
on the moment curve), our method gives substantially better bounds. The construction
yields an algorithm to construct such weak ε-nets in time O(n ln(1/ε)). We also
prove, by a different method, a near-linear upper bound for points uniformly distributed
on the (d - 1)-dimensional sphere.
article_processing_charge: No
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Matoušek J, Wagner U. New constructions of weak epsilon-nets. In: Proceedings
of the Nineteenth Annual Symposium on Computational Geometry. Association
for Computing Machinery; 2003:129-135. doi:10.1145/777792.777813'
apa: 'Matoušek, J., & Wagner, U. (2003). New constructions of weak epsilon-nets.
In Proceedings of the nineteenth annual symposium on Computational geometry
(pp. 129–135). San Diego, CA, United States: Association for Computing Machinery.
https://doi.org/10.1145/777792.777813'
chicago: Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak Epsilon-Nets.”
In Proceedings of the Nineteenth Annual Symposium on Computational Geometry,
129–35. Association for Computing Machinery, 2003. https://doi.org/10.1145/777792.777813.
ieee: J. Matoušek and U. Wagner, “New constructions of weak epsilon-nets,” in Proceedings
of the nineteenth annual symposium on Computational geometry, San Diego, CA,
United States, 2003, pp. 129–135.
ista: 'Matoušek J, Wagner U. 2003. New constructions of weak epsilon-nets. Proceedings
of the nineteenth annual symposium on Computational geometry. SoCG: Symposium
on Computational Geometry, 129–135.'
mla: Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak Epsilon-Nets.” Proceedings
of the Nineteenth Annual Symposium on Computational Geometry, Association
for Computing Machinery, 2003, pp. 129–35, doi:10.1145/777792.777813.
short: J. Matoušek, U. Wagner, in:, Proceedings of the Nineteenth Annual Symposium
on Computational Geometry, Association for Computing Machinery, 2003, pp. 129–135.
conference:
end_date: 2003-06-10
location: San Diego, CA, United States
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2003-06-08
date_created: 2018-12-11T11:57:34Z
date_published: 2003-06-08T00:00:00Z
date_updated: 2026-05-28T08:11:49Z
day: '08'
doi: 10.1145/777792.777813
extern: '1'
fulldoi: https://doi.org/10.1145/777792.777813
language:
- iso: eng
month: '06'
oa_version: None
page: 129 - 135
publication: Proceedings of the nineteenth annual symposium on Computational geometry
publication_identifier:
isbn:
- '9781581136630'
publication_status: published
publisher: Association for Computing Machinery
publist_id: '4502'
quality_controlled: '1'
status: public
title: New constructions of weak epsilon-nets
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2003'
...
---
OA_place: publisher
OA_type: free access
_id: '3556'
abstract:
- lang: eng
text: We define the Morse-Smale complex of a Morse function over a 3-manifold as
the overlay of the descending and as- cending manifolds of all critical points.
In the generic case, its 3-dimensional cells are shaped like crystals and are
sepa- rated by quadrangular faces. In this paper, we give a combi- natorial algorithm
for constructing such complexes for piece- wise linear data.
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: John
full_name: Harer, John
last_name: Harer
- first_name: Vijay
full_name: Natarajan, Vijay
last_name: Natarajan
- first_name: Valerio
full_name: Pascucci, Valerio
last_name: Pascucci
citation:
ama: 'Edelsbrunner H, Harer J, Natarajan V, Pascucci V. Morse-Smale complexes for
piecewise linear 3-manifolds. In: Proceedings of the Nineteenth Annual Symposium
in Computional Geometry. Association for Computing Machinery; 2003:361-370.
doi:10.1145/777792.777846'
apa: 'Edelsbrunner, H., Harer, J., Natarajan, V., & Pascucci, V. (2003). Morse-Smale
complexes for piecewise linear 3-manifolds. In Proceedings of the nineteenth
annual symposium in Computional geometry (pp. 361–370). San Diego, CA, United
States: Association for Computing Machinery. https://doi.org/10.1145/777792.777846'
chicago: Edelsbrunner, Herbert, John Harer, Vijay Natarajan, and Valerio Pascucci.
“Morse-Smale Complexes for Piecewise Linear 3-Manifolds.” In Proceedings of
the Nineteenth Annual Symposium in Computional Geometry, 361–70. Association
for Computing Machinery, 2003. https://doi.org/10.1145/777792.777846.
ieee: H. Edelsbrunner, J. Harer, V. Natarajan, and V. Pascucci, “Morse-Smale complexes
for piecewise linear 3-manifolds,” in Proceedings of the nineteenth annual
symposium in Computional geometry, San Diego, CA, United States, 2003, pp.
361–370.
ista: 'Edelsbrunner H, Harer J, Natarajan V, Pascucci V. 2003. Morse-Smale complexes
for piecewise linear 3-manifolds. Proceedings of the nineteenth annual symposium
in Computional geometry. SCG: Symposium on Computational Geometry, 361–370.'
mla: Edelsbrunner, Herbert, et al. “Morse-Smale Complexes for Piecewise Linear 3-Manifolds.”
Proceedings of the Nineteenth Annual Symposium in Computional Geometry,
Association for Computing Machinery, 2003, pp. 361–70, doi:10.1145/777792.777846.
short: H. Edelsbrunner, J. Harer, V. Natarajan, V. Pascucci, in:, Proceedings of
the Nineteenth Annual Symposium in Computional Geometry, Association for Computing
Machinery, 2003, pp. 361–370.
conference:
end_date: 2003-10-26
location: San Diego, CA, United States
name: 'SCG: Symposium on Computational Geometry'
start_date: 2003-08-06
date_created: 2018-12-11T12:03:57Z
date_published: 2003-06-08T00:00:00Z
date_updated: 2026-05-20T14:15:30Z
day: '08'
doi: 10.1145/777792.777846
extern: '1'
fulldoi: https://doi.org/10.1145/777792.777846
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1145/777792.777846
month: '06'
oa: 1
oa_version: Accepted Version
page: 361 - 370
publication: Proceedings of the nineteenth annual symposium in Computional geometry
publication_identifier:
isbn:
- '9781581136630'
publication_status: published
publisher: Association for Computing Machinery
publist_id: '2829'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Morse-Smale complexes for piecewise linear 3-manifolds
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2003'
...