An optimal algorithm for computing angle-constrained spanners
Let <em>S</em> be a set of <em>n</em> points in R<sup><em>d</em></sup> and let <em>t</em>>1 be a real number. A graph <em>G</em>=(<em>S</em>,<em>E</em>) is called a <em>t</em>-spanner f...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Carleton University
2012-11-01
|
| Series: | Journal of Computational Geometry |
| Online Access: | http://jocg.org/index.php/jocg/article/view/94 |
| _version_ | 1819085910733488128 |
|---|---|
| author | Paz Carmi Michiel Smid |
| author_facet | Paz Carmi Michiel Smid |
| author_sort | Paz Carmi |
| collection | DOAJ |
| description | Let <em>S</em> be a set of <em>n</em> points in R<sup><em>d</em></sup> and let <em>t</em>>1 be a real number. A graph <em>G</em>=(<em>S</em>,<em>E</em>) is called a <em>t</em>-spanner for <em>S</em>, if for any two points <em>p</em> and <em>q</em> in <em>S</em>, the shortest-path distance in <em>G</em> between <em>p</em> and<em>q</em> is at most <em>t</em>|<em>pq</em>|, where |<em>pq</em>| denotes the Euclidean distance between <em>p</em> and <em>q</em>. The graph <em>G</em> is called θ-angle-constrained, if any two distinct edges sharing an endpoint make an angle of at least θ. It is shown that, for any θ with 0<θ<π/3, a θ-angle-constrained <em>t</em>-spanner can be computed in <em>O</em>(<em>n</em>log <em>n</em>) time, where <em>t</em> depends only on θ. For values of θ approaching 0, we have<em>t</em>=1 + <em>O</em>(θ). |
| first_indexed | 2024-12-21T21:11:52Z |
| format | Article |
| id | doaj.art-9d8f5c1eec9d4f7b9ec5b9851c4c7f16 |
| institution | Directory Open Access Journal |
| issn | 1920-180X |
| language | English |
| last_indexed | 2024-12-21T21:11:52Z |
| publishDate | 2012-11-01 |
| publisher | Carleton University |
| record_format | Article |
| series | Journal of Computational Geometry |
| spelling | doaj.art-9d8f5c1eec9d4f7b9ec5b9851c4c7f162022-12-21T18:50:07ZengCarleton UniversityJournal of Computational Geometry1920-180X2012-11-013110.20382/jocg.v3i1a1032An optimal algorithm for computing angle-constrained spannersPaz CarmiMichiel SmidLet <em>S</em> be a set of <em>n</em> points in R<sup><em>d</em></sup> and let <em>t</em>>1 be a real number. A graph <em>G</em>=(<em>S</em>,<em>E</em>) is called a <em>t</em>-spanner for <em>S</em>, if for any two points <em>p</em> and <em>q</em> in <em>S</em>, the shortest-path distance in <em>G</em> between <em>p</em> and<em>q</em> is at most <em>t</em>|<em>pq</em>|, where |<em>pq</em>| denotes the Euclidean distance between <em>p</em> and <em>q</em>. The graph <em>G</em> is called θ-angle-constrained, if any two distinct edges sharing an endpoint make an angle of at least θ. It is shown that, for any θ with 0<θ<π/3, a θ-angle-constrained <em>t</em>-spanner can be computed in <em>O</em>(<em>n</em>log <em>n</em>) time, where <em>t</em> depends only on θ. For values of θ approaching 0, we have<em>t</em>=1 + <em>O</em>(θ).http://jocg.org/index.php/jocg/article/view/94 |
| spellingShingle | Paz Carmi Michiel Smid An optimal algorithm for computing angle-constrained spanners Journal of Computational Geometry |
| title | An optimal algorithm for computing angle-constrained spanners |
| title_full | An optimal algorithm for computing angle-constrained spanners |
| title_fullStr | An optimal algorithm for computing angle-constrained spanners |
| title_full_unstemmed | An optimal algorithm for computing angle-constrained spanners |
| title_short | An optimal algorithm for computing angle-constrained spanners |
| title_sort | optimal algorithm for computing angle constrained spanners |
| url | http://jocg.org/index.php/jocg/article/view/94 |
| work_keys_str_mv | AT pazcarmi anoptimalalgorithmforcomputingangleconstrainedspanners AT michielsmid anoptimalalgorithmforcomputingangleconstrainedspanners AT pazcarmi optimalalgorithmforcomputingangleconstrainedspanners AT michielsmid optimalalgorithmforcomputingangleconstrainedspanners |