File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.ipl.2006.09.014
- Scopus: eid_2-s2.0-33846065043
- WOS: WOS:000244216900005
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: A linear time algorithm for max-min length triangulation of a convex polygon
Title | A linear time algorithm for max-min length triangulation of a convex polygon |
---|---|
Authors | |
Keywords | Computational geometry Max-min length k-set triangulation Max-min length triangulation |
Issue Date | 2007 |
Citation | Information Processing Letters, 2007, v. 101, n. 5, p. 203-208 How to Cite? |
Abstract | We consider the following planar max-min length triangulation problem: given a set of n points in the Euclidean plane, find a triangulation such that the length of the shortest edge in the triangulation is maximized. In this paper, a linear time algorithm is proposed for computing the max-min length triangulation of a set of points in convex position. In addition, an O (n log n) time algorithm is proposed for computing the max-min length k-set triangulation of a set of points in convex position, where we are to compute a set of k vertices such that the max-min length triangulation on them is minimized over all possible k-set. We further show that the graph version of max-min length triangulation is NP-complete, and some common heuristics such as greedy algorithm are in general not able to give a bounded-ratio approximation to the max-min length triangulation. © 2006. |
Persistent Identifier | http://hdl.handle.net/10722/336032 |
ISSN | 2023 Impact Factor: 0.7 2023 SCImago Journal Rankings: 0.404 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hu, Shiyan | - |
dc.date.accessioned | 2024-01-15T08:22:11Z | - |
dc.date.available | 2024-01-15T08:22:11Z | - |
dc.date.issued | 2007 | - |
dc.identifier.citation | Information Processing Letters, 2007, v. 101, n. 5, p. 203-208 | - |
dc.identifier.issn | 0020-0190 | - |
dc.identifier.uri | http://hdl.handle.net/10722/336032 | - |
dc.description.abstract | We consider the following planar max-min length triangulation problem: given a set of n points in the Euclidean plane, find a triangulation such that the length of the shortest edge in the triangulation is maximized. In this paper, a linear time algorithm is proposed for computing the max-min length triangulation of a set of points in convex position. In addition, an O (n log n) time algorithm is proposed for computing the max-min length k-set triangulation of a set of points in convex position, where we are to compute a set of k vertices such that the max-min length triangulation on them is minimized over all possible k-set. We further show that the graph version of max-min length triangulation is NP-complete, and some common heuristics such as greedy algorithm are in general not able to give a bounded-ratio approximation to the max-min length triangulation. © 2006. | - |
dc.language | eng | - |
dc.relation.ispartof | Information Processing Letters | - |
dc.subject | Computational geometry | - |
dc.subject | Max-min length k-set triangulation | - |
dc.subject | Max-min length triangulation | - |
dc.title | A linear time algorithm for max-min length triangulation of a convex polygon | - |
dc.type | Article | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.ipl.2006.09.014 | - |
dc.identifier.scopus | eid_2-s2.0-33846065043 | - |
dc.identifier.volume | 101 | - |
dc.identifier.issue | 5 | - |
dc.identifier.spage | 203 | - |
dc.identifier.epage | 208 | - |
dc.identifier.isi | WOS:000244216900005 | - |