File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10898-009-9409-z
- Scopus: eid_2-s2.0-72449153011
- WOS: WOS:000272375600005
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: A new asymmetric inclusion region for minimum weight triangulation
| Title | A new asymmetric inclusion region for minimum weight triangulation |
|---|---|
| Authors | |
| Keywords | Inclusion region Minimum weight triangulation One-sided β-skeleton |
| Issue Date | 2010 |
| Citation | Journal of Global Optimization, 2010, v. 46, n. 1, p. 63-73 How to Cite? |
| Abstract | As a global optimization problem, planar minimum weight triangulation problem has attracted extensive research attention. In this paper, a new asymmetric graph called one-sided β-skeleton is introduced. We show that the one-sided circle-disconnected (√ 2 β) -skeleton is a subgraph of a minimum weight triangulation. An algorithm for identifying subgraph of minimum weight triangulation using the one-sided (√ 2 β) -skeleton is proposed and it runs in {O(n4/3+ε+min{κ log n, n 2log n}) time, where κ is the number of intersected segmented between the complete graph and the greedy triangulation of the point set. © 2009 Springer Science+Business Media, LLC. |
| Persistent Identifier | http://hdl.handle.net/10722/336078 |
| ISSN | 2023 Impact Factor: 1.3 2023 SCImago Journal Rankings: 0.743 |
| ISI Accession Number ID |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Hu, Shiyan | - |
| dc.date.accessioned | 2024-01-15T08:23:14Z | - |
| dc.date.available | 2024-01-15T08:23:14Z | - |
| dc.date.issued | 2010 | - |
| dc.identifier.citation | Journal of Global Optimization, 2010, v. 46, n. 1, p. 63-73 | - |
| dc.identifier.issn | 0925-5001 | - |
| dc.identifier.uri | http://hdl.handle.net/10722/336078 | - |
| dc.description.abstract | As a global optimization problem, planar minimum weight triangulation problem has attracted extensive research attention. In this paper, a new asymmetric graph called one-sided β-skeleton is introduced. We show that the one-sided circle-disconnected (√ 2 β) -skeleton is a subgraph of a minimum weight triangulation. An algorithm for identifying subgraph of minimum weight triangulation using the one-sided (√ 2 β) -skeleton is proposed and it runs in {O(n4/3+ε+min{κ log n, n 2log n}) time, where κ is the number of intersected segmented between the complete graph and the greedy triangulation of the point set. © 2009 Springer Science+Business Media, LLC. | - |
| dc.language | eng | - |
| dc.relation.ispartof | Journal of Global Optimization | - |
| dc.subject | Inclusion region | - |
| dc.subject | Minimum weight triangulation | - |
| dc.subject | One-sided β-skeleton | - |
| dc.title | A new asymmetric inclusion region for minimum weight triangulation | - |
| dc.type | Article | - |
| dc.description.nature | link_to_subscribed_fulltext | - |
| dc.identifier.doi | 10.1007/s10898-009-9409-z | - |
| dc.identifier.scopus | eid_2-s2.0-72449153011 | - |
| dc.identifier.volume | 46 | - |
| dc.identifier.issue | 1 | - |
| dc.identifier.spage | 63 | - |
| dc.identifier.epage | 73 | - |
| dc.identifier.eissn | 1573-2916 | - |
| dc.identifier.isi | WOS:000272375600005 | - |