Polytope Containment and Determination by Linear Probes
Identifieur interne : 001C34 ( Istex/Corpus ); précédent : 001C33; suivant : 001C35Polytope Containment and Determination by Linear Probes
Auteurs : Peter Gritzmann ; Victor Klee ; John WestwaterSource :
- Proceedings of the London Mathematical Society [ 0024-6115 ] ; 1995-05.
Abstract
As the terms are used here, a body in Rd is a compact convex set with non-empty interior, and a polytope is a body that has only finitely many extreme points. The class of all bodies whose interior includes the origin 0 is denoted by C0d. A set X is symmetric if X = −X. The ray-oracle of a body C ∈ C0d is the function Oc which, accepting as input an arbitrary ray R issuing from 0, produces the point at which R intersects the boundary of C. This paper is concerned with a few central aspects of the following general question: given certain information about C, what additional information can be obtained by questioning the ray-oracle, and how efficiently can it be obtained? It is assumed that infinite-precision real arithmetic and the usual vector operations in Rd are available at no cost, so the efficiency of an algorithm is measured solely in terms of its number of calls to the ray-oracle. The paper discusses two main problems, the first of which—the containment problem—arose from a question in abstract numerical analysis. Here the goal is to construct a polytope P(not necessarily in any sense a small one) that contains C, where this requires precise specification of the vertices of P. There are some sharp positive results for the case in which d = 2 and C is known not to be too asymmetric, but the main result on the containment problem is negative. It asserts that when d ≥ 3 and the body is known only to be rotund and symmetric, there is no algorithm for the containment problem. This is the case even when there is available a certain master oracle whose question-answering power far exceeds that of the ray-oracle. However, it turns out that even when there is no additional information about C, the following relaxation of the containment problem admits an algorithmic solution based solely on the ray-oracle: construct a polytope containing C or conclude that the centred condition number of C exceeds a prescribed bound. In the other main problem—the reconstruction problem— it is known only that C is itself a polytope and the problem is to construct C with the aid of a finite number of calls to the ray-oracle. That is accomplished with a number of calls that depends on the number of faces (and hence on the ‘combinatorial complexity’) of C.
Url:
DOI: 10.1112/plms/s3-70.3.691
Links to Exploration step
ISTEX:856BA6A87C7978655B8F4ABE490D993C93B21BD7Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Polytope Containment and Determination by Linear Probes</title><author><name sortKey="Gritzmann, Peter" sort="Gritzmann, Peter" uniqKey="Gritzmann P" first="Peter" last="Gritzmann">Peter Gritzmann</name><affiliation><mods:affiliation>Universität Trier Fb IV, Mathematik, D-54286 Trier, Germany E-mail: gritzman@dml.uni-trier.de</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: gritzman@dml.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Klee, Victor" sort="Klee, Victor" uniqKey="Klee V" first="Victor" last="Klee">Victor Klee</name><affiliation><mods:affiliation>Department of Mathematics, University of Washington Seattle, Washington 98195-0001 U.S.A E-mail: klee@math.washington.edu johnw@math.washington.edu</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: klee@math.washington.edu</mods:affiliation></affiliation></author><author><name sortKey="Westwater, John" sort="Westwater, John" uniqKey="Westwater J" first="John" last="Westwater">John Westwater</name><affiliation><mods:affiliation>Department of Mathematics, University of Washington Seattle, Washington 98195-0001 U.S.A E-mail: klee@math.washington.edu johnw@math.washington.edu</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: klee@math.washington.edu</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:856BA6A87C7978655B8F4ABE490D993C93B21BD7</idno><date when="1995" year="1995">1995</date><idno type="doi">10.1112/plms/s3-70.3.691</idno><idno type="url">https://api.istex.fr/document/856BA6A87C7978655B8F4ABE490D993C93B21BD7/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001C34</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001C34</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Polytope Containment and Determination by Linear Probes</title><author><name sortKey="Gritzmann, Peter" sort="Gritzmann, Peter" uniqKey="Gritzmann P" first="Peter" last="Gritzmann">Peter Gritzmann</name><affiliation><mods:affiliation>Universität Trier Fb IV, Mathematik, D-54286 Trier, Germany E-mail: gritzman@dml.uni-trier.de</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: gritzman@dml.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Klee, Victor" sort="Klee, Victor" uniqKey="Klee V" first="Victor" last="Klee">Victor Klee</name><affiliation><mods:affiliation>Department of Mathematics, University of Washington Seattle, Washington 98195-0001 U.S.A E-mail: klee@math.washington.edu johnw@math.washington.edu</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: klee@math.washington.edu</mods:affiliation></affiliation></author><author><name sortKey="Westwater, John" sort="Westwater, John" uniqKey="Westwater J" first="John" last="Westwater">John Westwater</name><affiliation><mods:affiliation>Department of Mathematics, University of Washington Seattle, Washington 98195-0001 U.S.A E-mail: klee@math.washington.edu johnw@math.washington.edu</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: klee@math.washington.edu</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Proceedings of the London Mathematical Society</title><idno type="ISSN">0024-6115</idno><idno type="eISSN">1460-244X</idno><imprint><publisher>Oxford University Press</publisher><date type="published" when="1995-05">1995-05</date><biblScope unit="volume">s3-70</biblScope><biblScope unit="issue">3</biblScope><biblScope unit="page" from="691">691</biblScope><biblScope unit="page" to="720">720</biblScope></imprint><idno type="ISSN">0024-6115</idno></series><idno type="istex">856BA6A87C7978655B8F4ABE490D993C93B21BD7</idno><idno type="DOI">10.1112/plms/s3-70.3.691</idno><idno type="ArticleID">s3-70.3.691</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0024-6115</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract">As the terms are used here, a body in Rd is a compact convex set with non-empty interior, and a polytope is a body that has only finitely many extreme points. The class of all bodies whose interior includes the origin 0 is denoted by C0d. A set X is symmetric if X = −X. The ray-oracle of a body C ∈ C0d is the function Oc which, accepting as input an arbitrary ray R issuing from 0, produces the point at which R intersects the boundary of C. This paper is concerned with a few central aspects of the following general question: given certain information about C, what additional information can be obtained by questioning the ray-oracle, and how efficiently can it be obtained? It is assumed that infinite-precision real arithmetic and the usual vector operations in Rd are available at no cost, so the efficiency of an algorithm is measured solely in terms of its number of calls to the ray-oracle. The paper discusses two main problems, the first of which—the containment problem—arose from a question in abstract numerical analysis. Here the goal is to construct a polytope P(not necessarily in any sense a small one) that contains C, where this requires precise specification of the vertices of P. There are some sharp positive results for the case in which d = 2 and C is known not to be too asymmetric, but the main result on the containment problem is negative. It asserts that when d ≥ 3 and the body is known only to be rotund and symmetric, there is no algorithm for the containment problem. This is the case even when there is available a certain master oracle whose question-answering power far exceeds that of the ray-oracle. However, it turns out that even when there is no additional information about C, the following relaxation of the containment problem admits an algorithmic solution based solely on the ray-oracle: construct a polytope containing C or conclude that the centred condition number of C exceeds a prescribed bound. In the other main problem—the reconstruction problem— it is known only that C is itself a polytope and the problem is to construct C with the aid of a finite number of calls to the ray-oracle. That is accomplished with a number of calls that depends on the number of faces (and hence on the ‘combinatorial complexity’) of C.</div></front></TEI><istex><corpusName>oup</corpusName><author><json:item><name>Peter Gritzmann</name><affiliations><json:string>Universität Trier Fb IV, Mathematik, D-54286 Trier, Germany E-mail: gritzman@dml.uni-trier.de</json:string><json:string>E-mail: gritzman@dml.uni-trier.de</json:string></affiliations></json:item><json:item><name>Victor Klee</name><affiliations><json:string>Department of Mathematics, University of Washington Seattle, Washington 98195-0001 U.S.A E-mail: klee@math.washington.edu johnw@math.washington.edu</json:string><json:string>E-mail: klee@math.washington.edu</json:string></affiliations></json:item><json:item><name>John Westwater</name><affiliations><json:string>Department of Mathematics, University of Washington Seattle, Washington 98195-0001 U.S.A E-mail: klee@math.washington.edu johnw@math.washington.edu</json:string><json:string>E-mail: klee@math.washington.edu</json:string></affiliations></json:item></author><subject><json:item><value>Articles</value></json:item></subject><articleId><json:string>s3-70.3.691</json:string></articleId><language><json:string>unknown</json:string></language><originalGenre><json:string>research-article</json:string></originalGenre><abstract>As the terms are used here, a body in Rd is a compact convex set with non-empty interior, and a polytope is a body that has only finitely many extreme points. The class of all bodies whose interior includes the origin 0 is denoted by C0d. A set X is symmetric if X = −X. The ray-oracle of a body C ∈ C0d is the function Oc which, accepting as input an arbitrary ray R issuing from 0, produces the point at which R intersects the boundary of C. This paper is concerned with a few central aspects of the following general question: given certain information about C, what additional information can be obtained by questioning the ray-oracle, and how efficiently can it be obtained? It is assumed that infinite-precision real arithmetic and the usual vector operations in Rd are available at no cost, so the efficiency of an algorithm is measured solely in terms of its number of calls to the ray-oracle. The paper discusses two main problems, the first of which—the containment problem—arose from a question in abstract numerical analysis. Here the goal is to construct a polytope P(not necessarily in any sense a small one) that contains C, where this requires precise specification of the vertices of P. There are some sharp positive results for the case in which d = 2 and C is known not to be too asymmetric, but the main result on the containment problem is negative. It asserts that when d ≥ 3 and the body is known only to be rotund and symmetric, there is no algorithm for the containment problem. This is the case even when there is available a certain master oracle whose question-answering power far exceeds that of the ray-oracle. However, it turns out that even when there is no additional information about C, the following relaxation of the containment problem admits an algorithmic solution based solely on the ray-oracle: construct a polytope containing C or conclude that the centred condition number of C exceeds a prescribed bound. In the other main problem—the reconstruction problem— it is known only that C is itself a polytope and the problem is to construct C with the aid of a finite number of calls to the ray-oracle. That is accomplished with a number of calls that depends on the number of faces (and hence on the ‘combinatorial complexity’) of C.</abstract><qualityIndicators><score>10</score><pdfVersion>1.5</pdfVersion><pdfPageSize>451.44 x 697.68 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>1</keywordCount><abstractCharCount>2274</abstractCharCount><pdfWordCount>15164</pdfWordCount><pdfCharCount>70841</pdfCharCount><pdfPageCount>30</pdfPageCount><abstractWordCount>397</abstractWordCount></qualityIndicators><title>Polytope Containment and Determination by Linear Probes</title><refBibs><json:item><author><json:item><name>H,J Bernstein</name></json:item></author><host><volume>22</volume><pages><last>260</last><first>255</first></pages><author></author><title>Inform. Process. Lett</title><publicationDate>1986</publicationDate></host><title>Determining the shape of a convex /7-sided polygon by using 2n + k tactile probes</title><publicationDate>1986</publicationDate></json:item><json:item><author><json:item><name>E Bishop</name></json:item><json:item><name>D Bridges</name></json:item></author><host><author></author><title>Constructive analysis</title><publicationDate>1985</publicationDate></host><publicationDate>1985</publicationDate></json:item><json:item><author><json:item><name>A Bjorner</name></json:item><json:item><name>M Las</name></json:item><json:item><name>B Vergnas</name></json:item><json:item><name>N Sturmfels</name></json:item><json:item><name>G,M White</name></json:item><json:item><name> Ziegler</name></json:item></author><host><author></author><title>Theory of oriented matroids</title><publicationDate>1993</publicationDate></host><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>B Bollobas</name></json:item></author><host><volume>2</volume><pages><last>354</last><first>351</first></pages><author></author><title>Studia Sci. Math. Hungar</title><publicationDate>1967</publicationDate></host><title>Fixing systems for convex bodies</title><publicationDate>1967</publicationDate></json:item><json:item><author><json:item><name>R Cole</name></json:item><json:item><name>C,K Yap</name></json:item></author><host><volume>8</volume><pages><last>38</last><first>19</first></pages><author></author><title>J. Algorithms</title><publicationDate>1987</publicationDate></host><title>Shape from probing</title><publicationDate>1987</publicationDate></json:item><json:item><author><json:item><name>D,P Dobkin</name></json:item><json:item><name>H Edelsbrunner</name></json:item><json:item><name>C,K Yap</name></json:item></author><host><pages><last>432</last><first>424</first></pages><author></author><title>Proceedings of the \8th ACM Symposium on the Theory of Computing</title><publicationDate>1986</publicationDate></host><title>Probing convex polytopes</title><publicationDate>1986</publicationDate></json:item><json:item><host><pages><last>341</last><first>328</first></pages><author><json:item><name>D,P Dobkin</name></json:item><json:item><name>H Edelsbrunner</name></json:item><json:item><name>C,K Yap</name></json:item></author><title>Probing convex polytopes' (revised version of [6]), Autonomous robot vehicles (eds I</title><publicationDate>1990</publicationDate></host></json:item><json:item><author><json:item><name>H Edelsbrunner</name></json:item><json:item><name>J O 'rourke</name></json:item><json:item><name>R Seidel</name></json:item></author><host><volume>15</volume><pages><last>363</last><first>341</first></pages><author></author><title>SIAM J. Comput</title><publicationDate>1987</publicationDate></host><title>Constructing arrangements of lines and hyperplanes with applications'</title><publicationDate>1987</publicationDate></json:item><json:item><author><json:item><name>H Edelsbrunner</name></json:item><json:item><name>R Seidel</name></json:item><json:item><name>M Sharir</name></json:item></author><host><volume>555</volume><pages><last>123</last><first>108</first></pages><issue>22</issue><author></author><title>Lecture Notes in Computer Science SIAM J. Comput</title><publicationDate>1991</publicationDate></host><title>On the zone theorem for hyperplane arrangements', New results and trends in computer science</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>H Edelsbrunner</name></json:item><json:item><name>S,S Skiena</name></json:item></author><host><volume>17</volume><pages><last>882</last><first>870</first></pages><author></author><title>SIAM J. Comput</title><publicationDate>1988</publicationDate></host><title>Probing convex polygons with X-rays'</title><publicationDate>1988</publicationDate></json:item><json:item><author><json:item><name>R,E Ellis</name></json:item><json:item><name>E,M Riseman</name></json:item><json:item><name>A,R Hanson</name></json:item></author><host><volume>1</volume><pages><last>637</last><first>632</first></pages><author></author><title>Proc. Amer. Ass. Art. Intelligence Conf</title><publicationDate>1986</publicationDate></host><title>Tactile recognition by probing: identifying a polygon on a plane</title><publicationDate>1986</publicationDate></json:item><json:item><author><json:item><name>L Fejes-Toth</name></json:item><json:item><name>Ada On Primitive Polyhedra '</name></json:item><json:item><name> Math</name></json:item></author><host><volume>13</volume><pages><last>382</last><first>379</first></pages><author></author><title>Acad. Sci. Hungar</title><publicationDate>1962</publicationDate></host><publicationDate>1962</publicationDate></json:item><json:item><author><json:item><name>P,C Gaston</name></json:item><json:item><name>T Lozano-Perez</name></json:item></author><host><volume>6</volume><pages><last>266</last><first>257</first></pages><author></author><title>IEEE Trans. Pattern Recognition and Machine Intelligence</title><publicationDate>1984</publicationDate></host><title>Tactile recognition and localization using object models: the case of polyhedra on a plane</title><publicationDate>1984</publicationDate></json:item><json:item><author><json:item><name>W,E L Grimson</name></json:item><json:item><name>T Lozano-Perez</name></json:item></author><host><volume>3</volume><pages><last>35</last><first>3</first></pages><author></author><title>Internat. J. Robotics Research</title><publicationDate>1984</publicationDate></host><title>Model-based recognition and localization from sparse range or tactile data</title><publicationDate>1984</publicationDate></json:item><json:item><author><json:item><name>P Gritzmann</name></json:item><json:item><name>V Klee</name></json:item><json:item><name>J Westwater</name></json:item></author><host><pages><last>101</last><first>92</first></pages><author></author><title>Proceedings of the 6th ACM Symposium on Computational Geometry</title><publicationDate>1990</publicationDate></host><title>On the limited power of linear probes and other optimization oracles</title><publicationDate>1990</publicationDate></json:item><json:item><author><json:item><name>M Grotschel</name></json:item><json:item><name>L Lovasz</name></json:item><json:item><name>A Schruver</name></json:item></author><host><author></author><title>Geometric algorithms and combinatorial optimization</title><publicationDate>1988</publicationDate></host><publicationDate>1988</publicationDate></json:item><json:item><author><json:item><name>B Grunbaum</name></json:item></author><host><volume>15</volume><pages><last>163</last><first>161</first></pages><author></author><title>Acta Math. Acad. Sci. Hungar</title><publicationDate>1964</publicationDate></host><title>Fixing systems for inner illumination</title><publicationDate>1964</publicationDate></json:item><json:item><host><author><json:item><name>G,T Herman</name></json:item></author><title>Image reconstruction from projections: the fundamentals of computerized tomography</title><publicationDate>1980</publicationDate></host></json:item><json:item><author><json:item><name>S.-Y,R Li</name></json:item></author><host><volume>28</volume><pages><last>240</last><first>235</first></pages><author></author><title>Inform. Process. Lett</title><publicationDate>1988</publicationDate></host><title>Reconstruction of polygons from projections</title><publicationDate>1988</publicationDate></json:item><json:item><author><json:item><name>P Mani</name></json:item></author><host><volume>22</volume><pages><last>273</last><first>269</first></pages><author></author><title>Acta Math. Acad. Sci. Hungar</title><publicationDate>1971</publicationDate></host><publicationDate>1971</publicationDate></json:item><json:item><author><json:item><name>J,L Schneiter</name></json:item></author><host><pages><last>1267</last><first>1262</first></pages><author></author><title>IEEE Conf. Robotics Autom</title><publicationDate>1986</publicationDate></host><title>An objective tactile sensing strategy for object recognition and localization</title><publicationDate>1986</publicationDate></json:item><json:item><host><author><json:item><name>S,S Skiena</name></json:item><json:item><name> Geometric</name></json:item></author><publicationDate>1988</publicationDate></host></json:item><json:item><author><json:item><name>S,S Skiena</name></json:item></author><host><pages><last>605</last><first>599</first></pages><author></author><title>Problems in geometric probing', Algorithmica</title><publicationDate>1989</publicationDate></host><publicationDate>1989</publicationDate></json:item><json:item><author><json:item><name>S,S Skiena</name></json:item></author><host><volume>80</volume><pages><last>1383</last><first>1364</first></pages><author></author><title>IEEE Proceedings</title><publicationDate>1992</publicationDate></host><title>Interactive reconstruction via probing</title><publicationDate>1992</publicationDate></json:item></refBibs><genre><json:string>research-article</json:string></genre><host><volume>s3-70</volume><publisherId><json:string>plms</json:string></publisherId><pages><last>720</last><first>691</first></pages><issn><json:string>0024-6115</json:string></issn><issue>3</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><eissn><json:string>1460-244X</json:string></eissn><title>Proceedings of the London Mathematical Society</title></host><categories><wos><json:string>science</json:string><json:string>mathematics</json:string></wos><scienceMetrix></scienceMetrix></categories><publicationDate>1995</publicationDate><copyrightDate>1995</copyrightDate><doi><json:string>10.1112/plms/s3-70.3.691</json:string></doi><id>856BA6A87C7978655B8F4ABE490D993C93B21BD7</id><score>0.38487336</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/856BA6A87C7978655B8F4ABE490D993C93B21BD7/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/856BA6A87C7978655B8F4ABE490D993C93B21BD7/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/856BA6A87C7978655B8F4ABE490D993C93B21BD7/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Polytope Containment and Determination by Linear Probes</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Oxford University Press</publisher><availability><p>© The London Mathematical Society</p></availability><date>1995</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">Polytope Containment and Determination by Linear Probes</title><author xml:id="author-1"><persName><forename type="first">Peter</forename><surname>Gritzmann</surname></persName><email>gritzman@dml.uni-trier.de</email><email>gritzman@dml.uni-trier.de</email></author><author xml:id="author-2"><persName><forename type="first">Victor</forename><surname>Klee</surname></persName><email>klee@math.washington.edu johnw@math.washington.edu</email><email>klee@math.washington.edu</email></author><author xml:id="author-3"><persName><forename type="first">John</forename><surname>Westwater</surname></persName><email>klee@math.washington.edu johnw@math.washington.edu</email><email>klee@math.washington.edu</email></author></analytic><monogr><title level="j">Proceedings of the London Mathematical Society</title><idno type="pISSN">0024-6115</idno><idno type="eISSN">1460-244X</idno><imprint><publisher>Oxford University Press</publisher><date type="published" when="1995-05"></date><biblScope unit="volume">s3-70</biblScope><biblScope unit="issue">3</biblScope><biblScope unit="page" from="691">691</biblScope><biblScope unit="page" to="720">720</biblScope></imprint></monogr><idno type="istex">856BA6A87C7978655B8F4ABE490D993C93B21BD7</idno><idno type="DOI">10.1112/plms/s3-70.3.691</idno><idno type="ArticleID">s3-70.3.691</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1995</date></creation><abstract><p>As the terms are used here, a body in Rd is a compact convex set with non-empty interior, and a polytope is a body that has only finitely many extreme points. The class of all bodies whose interior includes the origin 0 is denoted by C0d. A set X is symmetric if X = −X. The ray-oracle of a body C ∈ C0d is the function Oc which, accepting as input an arbitrary ray R issuing from 0, produces the point at which R intersects the boundary of C. This paper is concerned with a few central aspects of the following general question: given certain information about C, what additional information can be obtained by questioning the ray-oracle, and how efficiently can it be obtained? It is assumed that infinite-precision real arithmetic and the usual vector operations in Rd are available at no cost, so the efficiency of an algorithm is measured solely in terms of its number of calls to the ray-oracle. The paper discusses two main problems, the first of which—the containment problem—arose from a question in abstract numerical analysis. Here the goal is to construct a polytope P(not necessarily in any sense a small one) that contains C, where this requires precise specification of the vertices of P. There are some sharp positive results for the case in which d = 2 and C is known not to be too asymmetric, but the main result on the containment problem is negative. It asserts that when d ≥ 3 and the body is known only to be rotund and symmetric, there is no algorithm for the containment problem. This is the case even when there is available a certain master oracle whose question-answering power far exceeds that of the ray-oracle. However, it turns out that even when there is no additional information about C, the following relaxation of the containment problem admits an algorithmic solution based solely on the ray-oracle: construct a polytope containing C or conclude that the centred condition number of C exceeds a prescribed bound. In the other main problem—the reconstruction problem— it is known only that C is itself a polytope and the problem is to construct C with the aid of a finite number of calls to the ray-oracle. That is accomplished with a number of calls that depends on the number of faces (and hence on the ‘combinatorial complexity’) of C.</p></abstract><textClass><keywords scheme="keyword"><list><item><term>Articles</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1995-05">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-12-22">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/856BA6A87C7978655B8F4ABE490D993C93B21BD7/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="corpus oup" wicri:toSee="no header"><istex:docType PUBLIC="-//NLM//DTD Journal Publishing DTD v2.3 20070202//EN" URI="journalpublishing.dtd" name="istex:docType"></istex:docType><istex:document><article article-type="research-article"><front><journal-meta><journal-id journal-id-type="hwp">plms</journal-id><journal-id journal-id-type="publisher-id">plms</journal-id><journal-id journal-id-type="pmc">plms</journal-id><journal-id journal-id-type="publisher">Proceedings of the London Mathematical Society</journal-id><journal-title>Proceedings of the London Mathematical Society</journal-title><issn pub-type="epub">1460-244X</issn><issn pub-type="ppub">0024-6115</issn><publisher><publisher-name>Oxford University Press</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="publisher-id">s3-70.3.691</article-id><article-id pub-id-type="doi">10.1112/plms/s3-70.3.691</article-id><article-categories><subj-group><subject>Articles</subject></subj-group></article-categories><title-group><article-title>Polytope Containment and Determination by Linear Probes</article-title></title-group><contrib-group><contrib contrib-type="author"><name><surname>Gritzmann</surname><given-names>Peter</given-names></name><xref ref-type="aff" rid="au1"></xref></contrib><contrib contrib-type="author"><name><surname>Klee</surname><given-names>Victor</given-names></name><xref ref-type="aff" rid="au2"></xref></contrib><contrib contrib-type="author"><name><surname>Westwater</surname><given-names>John</given-names></name><xref ref-type="aff" rid="au2"></xref></contrib><aff id="au1"><institution>Universität Trier</institution> <addr-line>Fb IV, Mathematik, D-54286 Trier, Germany</addr-line> E-mail: <email>gritzman@dml.uni-trier.de</email></aff><aff id="au2"><institution>Department of Mathematics, University of Washington</institution> <addr-line>Seattle, Washington 98195-0001 U.S.A</addr-line> E-mail: <email>klee@math.washington.edu</email> <email>johnw@math.washington.edu</email></aff></contrib-group><pub-date pub-type="ppub"><month>5</month><year>1995</year></pub-date><volume>s3-70</volume><issue>3</issue><fpage>691</fpage><lpage>720</lpage><history><date date-type="received"><day>08</day><month>12</month><year>1992</year></date><date date-type="rev-recd"><day>13</day><month>1</month><year>1994</year></date></history><copyright-statement>© The London Mathematical Society</copyright-statement><copyright-year>1995</copyright-year><abstract><p>As the terms are used here, a <italic>body</italic> in R<sup><italic>d</italic></sup> is a compact convex set with non-empty interior, and a <italic>polytope</italic> is a body that has only finitely many extreme points. The class of all bodies whose interior includes the origin 0 is denoted by <inline-formula><mml:math><mml:mrow><mml:msubsup><mml:mi>C</mml:mi><mml:mn>0</mml:mn><mml:mi>d</mml:mi></mml:msubsup></mml:mrow></mml:math></inline-formula>. A set <italic>X</italic> is <italic>symmetric</italic> if <italic>X</italic> = −<italic>X</italic>. The <italic>ray-oracle</italic> of a body <inline-formula><mml:math><mml:mrow><mml:mi>C</mml:mi><mml:mtext> </mml:mtext><mml:mi>∈</mml:mi><mml:mtext> </mml:mtext><mml:msubsup><mml:mi>C</mml:mi><mml:mn>0</mml:mn><mml:mi>d</mml:mi></mml:msubsup></mml:mrow></mml:math></inline-formula> is the function <italic>O<sub>c</sub></italic> which, accepting as input an arbitrary ray <italic>R</italic> issuing from 0, produces the point at which <italic>R</italic> intersects the boundary of <italic>C</italic>. This paper is concerned with a few central aspects of the following general question: given certain information about <italic>C</italic>, what additional information can be obtained by questioning the ray-oracle, and how efficiently can it be obtained? It is assumed that infinite-precision real arithmetic and the usual vector operations in R<sup><italic>d</italic></sup> are available at no cost, so the efficiency of an algorithm is measured solely in terms of its number of calls to the ray-oracle.</p><p>The paper discusses two main problems, the first of which—the <italic>containment problem</italic>—arose from a question in abstract numerical analysis. Here the goal is to <italic>construct</italic> a polytope <italic>P</italic>(not necessarily in any sense a small one) that contains <italic>C</italic>, where this requires precise specification of the vertices of <italic>P</italic>. There are some sharp positive results for the case in which <italic>d</italic> = 2 and <italic>C</italic> is known not to be too asymmetric, but the main result on the containment problem is negative. It asserts that when <italic>d</italic> ≥ 3 and the body is known only to be rotund and symmetric, there is no algorithm for the containment problem. This is the case even when there is available a certain master oracle whose question-answering power far exceeds that of the ray-oracle. However, it turns out that even when there is no additional information about <italic>C</italic>, the following relaxation of the containment problem admits an algorithmic solution based solely on the ray-oracle: construct a polytope containing <italic>C</italic> or conclude that the centred condition number of <italic>C</italic> exceeds a prescribed bound.</p><p>In the other main problem—the <italic>reconstruction problem</italic>— it is known only that <italic>C</italic> is itself a polytope and the problem is to construct <italic>C</italic> with the aid of a finite number of calls to the ray-oracle. That is accomplished with a number of calls that depends on the number of faces (and hence on the ‘combinatorial complexity’) of <italic>C</italic>.</p></abstract></article-meta></front></article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>Polytope Containment and Determination by Linear Probes</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Polytope Containment and Determination by Linear Probes</title></titleInfo><name type="personal"><namePart type="given">Peter</namePart><namePart type="family">Gritzmann</namePart><affiliation>Universität Trier Fb IV, Mathematik, D-54286 Trier, Germany E-mail: gritzman@dml.uni-trier.de</affiliation><affiliation>E-mail: gritzman@dml.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Victor</namePart><namePart type="family">Klee</namePart><affiliation>Department of Mathematics, University of Washington Seattle, Washington 98195-0001 U.S.A E-mail: klee@math.washington.edu johnw@math.washington.edu</affiliation><affiliation>E-mail: klee@math.washington.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="family">Westwater</namePart><affiliation>Department of Mathematics, University of Washington Seattle, Washington 98195-0001 U.S.A E-mail: klee@math.washington.edu johnw@math.washington.edu</affiliation><affiliation>E-mail: klee@math.washington.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="research-article"></genre><subject><topic>Articles</topic></subject><originInfo><publisher>Oxford University Press</publisher><dateIssued encoding="w3cdtf">1995-05</dateIssued><copyrightDate encoding="w3cdtf">1995</copyrightDate></originInfo><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract>As the terms are used here, a body in Rd is a compact convex set with non-empty interior, and a polytope is a body that has only finitely many extreme points. The class of all bodies whose interior includes the origin 0 is denoted by C0d. A set X is symmetric if X = −X. The ray-oracle of a body C ∈ C0d is the function Oc which, accepting as input an arbitrary ray R issuing from 0, produces the point at which R intersects the boundary of C. This paper is concerned with a few central aspects of the following general question: given certain information about C, what additional information can be obtained by questioning the ray-oracle, and how efficiently can it be obtained? It is assumed that infinite-precision real arithmetic and the usual vector operations in Rd are available at no cost, so the efficiency of an algorithm is measured solely in terms of its number of calls to the ray-oracle. The paper discusses two main problems, the first of which—the containment problem—arose from a question in abstract numerical analysis. Here the goal is to construct a polytope P(not necessarily in any sense a small one) that contains C, where this requires precise specification of the vertices of P. There are some sharp positive results for the case in which d = 2 and C is known not to be too asymmetric, but the main result on the containment problem is negative. It asserts that when d ≥ 3 and the body is known only to be rotund and symmetric, there is no algorithm for the containment problem. This is the case even when there is available a certain master oracle whose question-answering power far exceeds that of the ray-oracle. However, it turns out that even when there is no additional information about C, the following relaxation of the containment problem admits an algorithmic solution based solely on the ray-oracle: construct a polytope containing C or conclude that the centred condition number of C exceeds a prescribed bound. In the other main problem—the reconstruction problem— it is known only that C is itself a polytope and the problem is to construct C with the aid of a finite number of calls to the ray-oracle. That is accomplished with a number of calls that depends on the number of faces (and hence on the ‘combinatorial complexity’) of C.</abstract><relatedItem type="host"><titleInfo><title>Proceedings of the London Mathematical Society</title></titleInfo><genre type="journal">journal</genre><identifier type="ISSN">0024-6115</identifier><identifier type="eISSN">1460-244X</identifier><identifier type="PublisherID">plms</identifier><identifier type="PublisherID-hwp">plms</identifier><part><date>1995</date><detail type="volume"><caption>vol.</caption><number>s3-70</number></detail><detail type="issue"><caption>no.</caption><number>3</number></detail><extent unit="pages"><start>691</start><end>720</end></extent></part></relatedItem><identifier type="istex">856BA6A87C7978655B8F4ABE490D993C93B21BD7</identifier><identifier type="DOI">10.1112/plms/s3-70.3.691</identifier><identifier type="ArticleID">s3-70.3.691</identifier><accessCondition type="use and reproduction" contentType="copyright">© The London Mathematical Society</accessCondition><recordInfo><recordContentSource>OUP</recordContentSource></recordInfo></mods></metadata><annexes><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/856BA6A87C7978655B8F4ABE490D993C93B21BD7/annexes/pdf</uri></json:item></annexes><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001C34 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001C34 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:856BA6A87C7978655B8F4ABE490D993C93B21BD7
|texte= Polytope Containment and Determination by Linear Probes
}}
| This area was generated with Dilib version V0.6.31. |  |