On the worst-case complexity of the silhouette of a polytope

Helmut Alt; Marc Glisse; Xavier Goaoc

inria-00099478, version 1

On the worst-case complexity of the silhouette of a polytope

Helmut Alt^a^, 1, Marc Glisse ()^b^, 2, Xavier Goaoc ()^c^, 2

15th Canadian Conference on Computational Geometry - CCCG 2003 (2003) 4 p

Abstract: We give conditions under which the worst-case size of the silhouette of a polytope is sub-linear. We provide examples with linear size silhouette if any of these conditions is relaxed. Our bounds are the first non-trivial bounds for the worst-case complexity of silhouettes.

a – FREIE UNIVERSITäT BERLIN
b – ENS PARIS - LORIA
c – UNIVERSITE NANCY 2
1: Institute of Computer Science [Warszawa]
Polish Academy of Sciences
2: ISA (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)

inria-00099478, version 1
http://hal.inria.fr/inria-00099478
oai:hal.inria.fr:inria-00099478
From: Publications Loria <>
Submitted on: Tuesday, 26 September 2006 09:24:09
Updated on: Thursday, 28 September 2006 15:22:46

See detailed view

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="inria-00099478"><analytic>
<author><persName><forename>Helmut</forename><surname>Alt</surname></persName>
<affiliation>
<orgName type="team">Institute of Computer Science [Warszawa]</orgName>
<country>PL</country>
<orgName type="institution">Polish Academy of Sciences</orgName>
</affiliation>
</author>
<author><persName><forename>Marc</forename><surname>Glisse</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">ISA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Xavier</forename><surname>Goaoc</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">ISA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="a">On the worst-case complexity of the silhouette of a polytope</title></analytic><monogr><meeting>15th Canadian Conference on Computational Geometry - CCCG 2003</meeting><imprint><publisher>none</publisher><pubPlace><settlement>Halifax</settlement><country> Canada</country></pubPlace><biblScope type="publicationDate">2003-00-00</biblScope><biblScope type="pp">4 p</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00099478</idno></biblStruct>
</listBibl>
</listBibl>