Product range spaces, sensitive sampling, and derandomization

We introduce the concept of a {\em sensitive $\varepsilon$-approximation} and use it to derive a more efficient algorithm for computing $\varepsilon$-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. T...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1999, Vol.28 (5), p.1552-1575
Main Authors: BRÖNNIMANN, H, CHAZELLE, B, MATOUSEK, J
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied mathematics
Applied sciences
Approximation
Computer science
Computer science
control theory
systems
Convex and discrete geometry
Exact sciences and technology
Geometry
Grants
Mathematics
Scholarships & fellowships
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c299t-70d404c54895898ff5a76b1023b5641a29eefdc348e3ece1ec7d2a6babf21c433
cites cdi_FETCH-LOGICAL-c299t-70d404c54895898ff5a76b1023b5641a29eefdc348e3ece1ec7d2a6babf21c433
container_end_page 1575
container_issue 5
container_start_page 1552
container_title SIAM journal on computing
container_volume 28
creator BRÖNNIMANN, H
CHAZELLE, B
MATOUSEK, J
description We introduce the concept of a {\em sensitive $\varepsilon$-approximation} and use it to derive a more efficient algorithm for computing $\varepsilon$-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. This generalizes and simplifies results from previous works. Using these tools, we give a new deterministic algorithm for computing the convex hull of n points in $\mbox{\smallBbb R}^d$. The algorithm is obtained by derandomization of a randomized incremental algorithm, and its running time of O(nlog n + n{\lfloor d/2\rfloor})$ is optimal for any fixed dimension $d\geq 2$.
doi_str_mv 10.1137/S0097539796260321
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_919112500</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2575972151</sourcerecordid><originalsourceid>FETCH-LOGICAL-c299t-70d404c54895898ff5a76b1023b5641a29eefdc348e3ece1ec7d2a6babf21c433</originalsourceid><addsrcrecordid>eNplkEtLA0EQhAdRMEZ_gLdFPLraPY-dnYMHCb4goKCel9l5hAnJ7jqzEfTXOyEBD54aur6qpouQc4RrRCZv3gCUFExJVdEKGMUDMkFQopSIeEgmW7nc6sfkJKUlAHKObEJuX2NvN2Ysou4WrkiDNi5dFcl1KYzhK2_0eliFbnFV6M4W1mXO9uvwo8fQd6fkyOtVcmf7OSUfD_fvs6dy_vL4PLubl4YqNZYSLAduBK-VqFXtvdCyahEoa0XFUVPlnLeG8doxZxw6Iy3VVatbT9FwxqbkYpc7xP5z49LYLPtN7PLJRqFCpAIgQ7iDTOxTis43QwxrHb8bhGZbUvOvpOy53AfrZPTK5-9MSH_GjHIQ7Bdl_mXr</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>919112500</pqid></control><display><type>article</type><title>Product range spaces, sensitive sampling, and derandomization</title><source>SIAM Journals Archive</source><source>Business Source Ultimate【Trial: -2024/12/31】【Remote access available】</source><source>ABI/INFORM Global</source><creator>BRÖNNIMANN, H ; CHAZELLE, B ; MATOUSEK, J</creator><creatorcontrib>BRÖNNIMANN, H ; CHAZELLE, B ; MATOUSEK, J</creatorcontrib><description>We introduce the concept of a {\em sensitive $\varepsilon$-approximation} and use it to derive a more efficient algorithm for computing $\varepsilon$-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. This generalizes and simplifies results from previous works. Using these tools, we give a new deterministic algorithm for computing the convex hull of n points in $\mbox{\smallBbb R}^d$. The algorithm is obtained by derandomization of a randomized incremental algorithm, and its running time of O(nlog n + n{\lfloor d/2\rfloor})$ is optimal for any fixed dimension $d\geq 2$.</description><identifier>ISSN: 0097-5397</identifier><identifier>EISSN: 1095-7111</identifier><identifier>DOI: 10.1137/S0097539796260321</identifier><language>eng</language><publisher>Philadelphia, PA: Society for Industrial and Applied Mathematics</publisher><subject>Algorithmics. Computability. Computer arithmetics ; Algorithms ; Applied mathematics ; Applied sciences ; Approximation ; Computer science ; Computer science; control theory; systems ; Convex and discrete geometry ; Exact sciences and technology ; Geometry ; Grants ; Mathematics ; Scholarships &amp; fellowships ; Sciences and techniques of general use ; Theoretical computing</subject><ispartof>SIAM journal on computing, 1999, Vol.28 (5), p.1552-1575</ispartof><rights>1999 INIST-CNRS</rights><rights>[Copyright] © 1999 Society for Industrial and Applied Mathematics</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c299t-70d404c54895898ff5a76b1023b5641a29eefdc348e3ece1ec7d2a6babf21c433</citedby><cites>FETCH-LOGICAL-c299t-70d404c54895898ff5a76b1023b5641a29eefdc348e3ece1ec7d2a6babf21c433</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/919112500?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,3185,4024,11688,27923,27924,27925,36060,44363</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=1979405$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>BRÖNNIMANN, H</creatorcontrib><creatorcontrib>CHAZELLE, B</creatorcontrib><creatorcontrib>MATOUSEK, J</creatorcontrib><title>Product range spaces, sensitive sampling, and derandomization</title><title>SIAM journal on computing</title><description>We introduce the concept of a {\em sensitive $\varepsilon$-approximation} and use it to derive a more efficient algorithm for computing $\varepsilon$-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. This generalizes and simplifies results from previous works. Using these tools, we give a new deterministic algorithm for computing the convex hull of n points in $\mbox{\smallBbb R}^d$. The algorithm is obtained by derandomization of a randomized incremental algorithm, and its running time of O(nlog n + n{\lfloor d/2\rfloor})$ is optimal for any fixed dimension $d\geq 2$.</description><subject>Algorithmics. Computability. Computer arithmetics</subject><subject>Algorithms</subject><subject>Applied mathematics</subject><subject>Applied sciences</subject><subject>Approximation</subject><subject>Computer science</subject><subject>Computer science; control theory; systems</subject><subject>Convex and discrete geometry</subject><subject>Exact sciences and technology</subject><subject>Geometry</subject><subject>Grants</subject><subject>Mathematics</subject><subject>Scholarships &amp; fellowships</subject><subject>Sciences and techniques of general use</subject><subject>Theoretical computing</subject><issn>0097-5397</issn><issn>1095-7111</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1999</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNplkEtLA0EQhAdRMEZ_gLdFPLraPY-dnYMHCb4goKCel9l5hAnJ7jqzEfTXOyEBD54aur6qpouQc4RrRCZv3gCUFExJVdEKGMUDMkFQopSIeEgmW7nc6sfkJKUlAHKObEJuX2NvN2Ysou4WrkiDNi5dFcl1KYzhK2_0eliFbnFV6M4W1mXO9uvwo8fQd6fkyOtVcmf7OSUfD_fvs6dy_vL4PLubl4YqNZYSLAduBK-VqFXtvdCyahEoa0XFUVPlnLeG8doxZxw6Iy3VVatbT9FwxqbkYpc7xP5z49LYLPtN7PLJRqFCpAIgQ7iDTOxTis43QwxrHb8bhGZbUvOvpOy53AfrZPTK5-9MSH_GjHIQ7Bdl_mXr</recordid><startdate>1999</startdate><enddate>1999</enddate><creator>BRÖNNIMANN, H</creator><creator>CHAZELLE, B</creator><creator>MATOUSEK, J</creator><general>Society for Industrial and Applied Mathematics</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7RQ</scope><scope>7WY</scope><scope>7WZ</scope><scope>7X2</scope><scope>7XB</scope><scope>87Z</scope><scope>88A</scope><scope>88F</scope><scope>88I</scope><scope>88K</scope><scope>8AL</scope><scope>8FE</scope><scope>8FG</scope><scope>8FH</scope><scope>8FK</scope><scope>8FL</scope><scope>8G5</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>ATCPS</scope><scope>AZQEC</scope><scope>BBNVY</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>BHPHI</scope><scope>CCPQU</scope><scope>D1I</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>KB.</scope><scope>L.-</scope><scope>L6V</scope><scope>LK8</scope><scope>M0C</scope><scope>M0K</scope><scope>M0N</scope><scope>M1Q</scope><scope>M2O</scope><scope>M2P</scope><scope>M2T</scope><scope>M7P</scope><scope>M7S</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PATMY</scope><scope>PDBOC</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>PYCSY</scope><scope>Q9U</scope><scope>S0W</scope><scope>U9A</scope></search><sort><creationdate>1999</creationdate><title>Product range spaces, sensitive sampling, and derandomization</title><author>BRÖNNIMANN, H ; CHAZELLE, B ; MATOUSEK, J</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c299t-70d404c54895898ff5a76b1023b5641a29eefdc348e3ece1ec7d2a6babf21c433</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1999</creationdate><topic>Algorithmics. Computability. Computer arithmetics</topic><topic>Algorithms</topic><topic>Applied mathematics</topic><topic>Applied sciences</topic><topic>Approximation</topic><topic>Computer science</topic><topic>Computer science; control theory; systems</topic><topic>Convex and discrete geometry</topic><topic>Exact sciences and technology</topic><topic>Geometry</topic><topic>Grants</topic><topic>Mathematics</topic><topic>Scholarships &amp; fellowships</topic><topic>Sciences and techniques of general use</topic><topic>Theoretical computing</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>BRÖNNIMANN, H</creatorcontrib><creatorcontrib>CHAZELLE, B</creatorcontrib><creatorcontrib>MATOUSEK, J</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>ProQuest Career &amp; Technical Education Database</collection><collection>ProQuest_ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>Agricultural Science Collection</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Biology Database (Alumni Edition)</collection><collection>Military Database (Alumni Edition)</collection><collection>Science Database (Alumni Edition)</collection><collection>Telecommunications (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Natural Science Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Research Library (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>Agricultural &amp; Environmental Science Collection</collection><collection>ProQuest Central Essentials</collection><collection>Biological Science Collection</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest Natural Science Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Materials Science Collection</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>https://resources.nclive.org/materials</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>ProQuest Biological Science Collection</collection><collection>ABI/INFORM Global</collection><collection>Agriculture Science Database</collection><collection>Computing Database</collection><collection>Military Database (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest_Research Library</collection><collection>ProQuest Science Journals</collection><collection>Telecommunications Database</collection><collection>ProQuest Biological Science Journals</collection><collection>Engineering Database</collection><collection>Research Library (Corporate)</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Environmental Science Database</collection><collection>Materials Science Collection</collection><collection>One Business (ProQuest)</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering Collection</collection><collection>Environmental Science Collection</collection><collection>ProQuest Central Basic</collection><collection>DELNET Engineering &amp; Technology Collection</collection><jtitle>SIAM journal on computing</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>BRÖNNIMANN, H</au><au>CHAZELLE, B</au><au>MATOUSEK, J</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Product range spaces, sensitive sampling, and derandomization</atitle><jtitle>SIAM journal on computing</jtitle><date>1999</date><risdate>1999</risdate><volume>28</volume><issue>5</issue><spage>1552</spage><epage>1575</epage><pages>1552-1575</pages><issn>0097-5397</issn><eissn>1095-7111</eissn><abstract>We introduce the concept of a {\em sensitive $\varepsilon$-approximation} and use it to derive a more efficient algorithm for computing $\varepsilon$-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. This generalizes and simplifies results from previous works. Using these tools, we give a new deterministic algorithm for computing the convex hull of n points in $\mbox{\smallBbb R}^d$. The algorithm is obtained by derandomization of a randomized incremental algorithm, and its running time of O(nlog n + n{\lfloor d/2\rfloor})$ is optimal for any fixed dimension $d\geq 2$.</abstract><cop>Philadelphia, PA</cop><pub>Society for Industrial and Applied Mathematics</pub><doi>10.1137/S0097539796260321</doi><tpages>24</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0097-5397
ispartof SIAM journal on computing, 1999, Vol.28 (5), p.1552-1575
issn 0097-5397
1095-7111
language eng
recordid cdi_proquest_journals_919112500
source SIAM Journals Archive; Business Source Ultimate【Trial: -2024/12/31】【Remote access available】; ABI/INFORM Global
subjects Algorithmics. Computability. Computer arithmetics
Algorithms
Applied mathematics
Applied sciences
Approximation
Computer science
Computer science
control theory
systems
Convex and discrete geometry
Exact sciences and technology
Geometry
Grants
Mathematics
Scholarships & fellowships
Sciences and techniques of general use
Theoretical computing
title Product range spaces, sensitive sampling, and derandomization
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T13%3A11%3A42IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Product%20range%20spaces,%20sensitive%20sampling,%20and%20derandomization&rft.jtitle=SIAM%20journal%20on%20computing&rft.au=BR%C3%96NNIMANN,%20H&rft.date=1999&rft.volume=28&rft.issue=5&rft.spage=1552&rft.epage=1575&rft.pages=1552-1575&rft.issn=0097-5397&rft.eissn=1095-7111&rft_id=info:doi/10.1137/S0097539796260321&rft_dat=%3Cproquest_cross%3E2575972151%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c299t-70d404c54895898ff5a76b1023b5641a29eefdc348e3ece1ec7d2a6babf21c433%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=919112500&rft_id=info:pmid/&rfr_iscdi=true