Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/11150Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Palios, L. | en |
| dc.date.accessioned | 2015-11-24T17:03:17Z | - |
| dc.date.available | 2015-11-24T17:03:17Z | - |
| dc.identifier.issn | 0302-9743 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11150 | - |
| dc.rights | Default Licence | - |
| dc.subject | motion planning | en |
| dc.subject | competitive algorithm | en |
| dc.subject | kernel | en |
| dc.subject | simple polygon | en |
| dc.subject | curve with increasing chords | en |
| dc.title | A new competitive strategy for reaching the kernel of an unknown polygon | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2000 | - |
| heal.abstract | We consider the following motion planning problem for a point robot inside a simple polygon P: starting from an arbitrary point s of P, the robot aims at reaching the closest point t of P from where the entire polygon P can be seen; the robot does not have complete knowledge of P but is equipped with a 360-degree vision system that helps it "see" its surrounding space. We are interested in a competitive path planning algorithm, i.e., one that produces a path whose length does not exceed a constant c times the length of the shortest off-line path tin this case, c x distance(s, t)); the constant c is called the competitive factor. In this paper, we present a new strategy that achieves a competitive factor of similar to3.126, improving over a 4.14-competitive strategy of Icking and Klein and a 3.829-competitive strategy of Lee et al. Our strategy possesses two additional advantages: first, the first point reached from where the entire polygon P is seen is precisely the closest such point to the starting position s, and second, all the points of the path are directly determined in terms of s and of polygon vertices, which implies that an actual robot following the strategy is not expected to deviate much from its course due to numerical error. The competitiveness analysis is based on properties of the class of curves with increasing chords. | en |
| heal.journalName | Algorithm Theory - Swat 2000 | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| palios-2000-A New Competitive Strategy.pdf | 165.7 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
