Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Competitive Exploration of Rectilinear Polygons
Department of Computer Science, Salerno University, Baronissi (SA) 84081, Italy.
Malmö högskola, School of Technology (TS).ORCID iD: 0000-0002-1342-8618
Malmö högskola, School of Technology (TS).
2006 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 354, no 3, p. 367-378Article in journal (Refereed) Published
Abstract [en]

Exploring a polygon with robots, when the robots do not have knowledge of the surroundings can be viewed as an online problem. Typical for online problems is that decisions must be made based on past events without complete information about the future. In our case the robots do not have complete information about the environment. Competitive analysis can be used to measure the performance of methods solving online problems. The competitive ratio of such a method is the ratio between the method's performance and the performance of the best method having full knowledge of the future. We are interested in obtaining good bounds on the competitive ratio of exploring polygons and prove constant competitive strategies and lower bounds for exploring a simple rectilinear polygon in the $L_1$ metric.

Place, publisher, year, edition, pages
Elsevier, 2006. Vol. 354, no 3, p. 367-378
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:mau:diva-2541DOI: 10.1016/j.tcs.2005.11.032ISI: 000236473600005Scopus ID: 2-s2.0-33644763997Local ID: 11304OAI: oai:DiVA.org:mau-2541DiVA, id: diva2:1399304
Conference
14th Symposium on Fundamentals of Computation Theory, Malmö, Sweden (August 13–15, 2003)
Available from: 2020-02-27 Created: 2020-02-27 Last updated: 2024-05-29Bibliographically approved

Open Access in DiVA

fulltext(264 kB)126 downloads
File information
File name FULLTEXT01.pdfFile size 264 kBChecksum SHA-512
77339164c33f8315f47f7c979a3f0b8b04245c274545bd38bf7299dfd0baa4d0650c40b879f4bce285bd5f08a15445297715b7b4bc6bc268abfadb610b36404e
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Nilsson, Bengt JPersson, Mia

Search in DiVA

By author/editor
Nilsson, Bengt JPersson, Mia
By organisation
School of Technology (TS)
In the same journal
Theoretical Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 127 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 68 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf