Drawing nice projections of objects in space
Identifieur interne : 001062 ( Istex/Checkpoint ); précédent : 001061; suivant : 001063Drawing nice projections of objects in space
Auteurs : Prosenjit Bose [Canada] ; Pedro Ramos [Espagne] ; Francisco Gomez [Espagne] ; Godfried Toussaint [Canada]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1996.
Abstract
Abstract: Our results on regular and minimum-crossing projections of line segments have immediate corollaries for polygonal chains, polygons, trees and more general geometric graphs in 3-D since these are all special cases of sets of line segments. Our results also have application to graph drawing for knot-theorists. Let K be a knot with n vertices. To study the knot's combinatorial properties, knot theorists obtain a planar graph G called the diagram of K by a regular projection of K. Many of their algorithms are applied to G and therefore their time complexity depends on the space complexity of G. By combining our algorithms we can obtain regular projections with the minimum number of crossings thereby minimizing the time complexity of their algorithms.
Url:
DOI: 10.1007/BFb0021790
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
ISTEX:199902040AE0924FDE67AEDBC7767DA79D3A916CLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Drawing nice projections of objects in space</title>
<author><name sortKey="Bose, Prosenjit" sort="Bose, Prosenjit" uniqKey="Bose P" first="Prosenjit" last="Bose">Prosenjit Bose</name>
</author>
<author><name sortKey="Ramos, Pedro" sort="Ramos, Pedro" uniqKey="Ramos P" first="Pedro" last="Ramos">Pedro Ramos</name>
</author>
<author><name sortKey="Gomez, Francisco" sort="Gomez, Francisco" uniqKey="Gomez F" first="Francisco" last="Gomez">Francisco Gomez</name>
</author>
<author><name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:199902040AE0924FDE67AEDBC7767DA79D3A916C</idno>
<date when="1996" year="1996">1996</date>
<idno type="doi">10.1007/BFb0021790</idno>
<idno type="url">https://api.istex.fr/document/199902040AE0924FDE67AEDBC7767DA79D3A916C/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001322</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001322</idno>
<idno type="wicri:Area/Istex/Curation">001210</idno>
<idno type="wicri:Area/Istex/Checkpoint">001062</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001062</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Drawing nice projections of objects in space</title>
<author><name sortKey="Bose, Prosenjit" sort="Bose, Prosenjit" uniqKey="Bose P" first="Prosenjit" last="Bose">Prosenjit Bose</name>
<affiliation wicri:level="1"><country xml:lang="fr">Canada</country>
<wicri:regionArea>University of British Columbia, Vancouver, British Columbia</wicri:regionArea>
<wicri:noRegion>British Columbia</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Ramos, Pedro" sort="Ramos, Pedro" uniqKey="Ramos P" first="Pedro" last="Ramos">Pedro Ramos</name>
<affiliation wicri:level="3"><country xml:lang="fr">Espagne</country>
<wicri:regionArea>Universidad Politecnica de Madrid, Madrid</wicri:regionArea>
<placeName><settlement type="city">Madrid</settlement>
<region nuts="2" type="region">Communauté de Madrid</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Gomez, Francisco" sort="Gomez, Francisco" uniqKey="Gomez F" first="Francisco" last="Gomez">Francisco Gomez</name>
<affiliation wicri:level="3"><country xml:lang="fr">Espagne</country>
<wicri:regionArea>Universidad Politecnica de Madrid, Madrid</wicri:regionArea>
<placeName><settlement type="city">Madrid</settlement>
<region nuts="2" type="region">Communauté de Madrid</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name>
<affiliation wicri:level="4"><country xml:lang="fr">Canada</country>
<wicri:regionArea>McGill University, Montreal, Quebec</wicri:regionArea>
<orgName type="university">Université McGill</orgName>
<placeName><settlement type="city">Montréal</settlement>
<region type="state">Québec</region>
</placeName>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>1996</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">199902040AE0924FDE67AEDBC7767DA79D3A916C</idno>
<idno type="DOI">10.1007/BFb0021790</idno>
<idno type="ChapterID">7</idno>
<idno type="ChapterID">Chap7</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: Our results on regular and minimum-crossing projections of line segments have immediate corollaries for polygonal chains, polygons, trees and more general geometric graphs in 3-D since these are all special cases of sets of line segments. Our results also have application to graph drawing for knot-theorists. Let K be a knot with n vertices. To study the knot's combinatorial properties, knot theorists obtain a planar graph G called the diagram of K by a regular projection of K. Many of their algorithms are applied to G and therefore their time complexity depends on the space complexity of G. By combining our algorithms we can obtain regular projections with the minimum number of crossings thereby minimizing the time complexity of their algorithms.</div>
</front>
</TEI>
<affiliations><list><country><li>Canada</li>
<li>Espagne</li>
</country>
<region><li>Communauté de Madrid</li>
<li>Québec</li>
</region>
<settlement><li>Madrid</li>
<li>Montréal</li>
</settlement>
<orgName><li>Université McGill</li>
</orgName>
</list>
<tree><country name="Canada"><noRegion><name sortKey="Bose, Prosenjit" sort="Bose, Prosenjit" uniqKey="Bose P" first="Prosenjit" last="Bose">Prosenjit Bose</name>
</noRegion>
<name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name>
</country>
<country name="Espagne"><region name="Communauté de Madrid"><name sortKey="Ramos, Pedro" sort="Ramos, Pedro" uniqKey="Ramos P" first="Pedro" last="Ramos">Pedro Ramos</name>
</region>
<name sortKey="Gomez, Francisco" sort="Gomez, Francisco" uniqKey="Gomez F" first="Francisco" last="Gomez">Francisco Gomez</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001062 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Checkpoint/biblio.hfd -nk 001062 | 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= Checkpoint |type= RBID |clé= ISTEX:199902040AE0924FDE67AEDBC7767DA79D3A916C |texte= Drawing nice projections of objects in space }}
![]() | This area was generated with Dilib version V0.6.31. | ![]() |