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).ORCID iD: 0000-0002-2316-2235
2003 (English)In: Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings / [ed] Andrzej Lingas; Bengt J. Nilsson, Springer , 2003, p. 234-245Conference paper, Published paper (Refereed)
Abstract [en]

Exploring a polygon with a robot, when the robot does not have a map of its surroundings can be viewed as an online problem. Typical for online problems is that you must make decisions based on past events without complete information about the future. In our case the robot does 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 upper bounds on the competitive ratio of exploring polygons and prove a 3/2-competitive strategy for exploring a simple rectilinear polygon in the L 1 metric.

Place, publisher, year, edition, pages
Springer , 2003. p. 234-245
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 2751
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:mau:diva-79008DOI: 10.1007/978-3-540-45077-1_22ISI: 000185822800022Scopus ID: 2-s2.0-35248864377ISBN: 978-3-540-40543-6 (print)ISBN: 978-3-540-45077-1 (print)OAI: oai:DiVA.org:mau-79008DiVA, id: diva2:1991665
Conference
14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003
Available from: 2025-08-25 Created: 2025-08-25 Last updated: 2026-02-17Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Nilsson, Bengt J.Persson, Mia

Search in DiVA

By author/editor
Nilsson, Bengt J.Persson, Mia
By organisation
School of Technology (TS)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 18 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