Publikationer från Malmö universitet
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Competitive Exploration of Rectilinear Polygons
Department of Computer Science, Salerno University, Baronissi (SA), 84081, Italy.
Malmö högskola, Teknik och samhälle (TS).ORCID-id: 0000-0002-1342-8618
Malmö högskola, Teknik och samhälle (TS).ORCID-id: 0000-0002-2316-2235
2003 (Engelska)Ingår i: Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings / [ed] Andrzej Lingas; Bengt J. Nilsson, Springer , 2003, s. 234-245Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Springer , 2003. s. 234-245
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 2751
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
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 (tryckt)ISBN: 978-3-540-45077-1 (tryckt)OAI: oai:DiVA.org:mau-79008DiVA, id: diva2:1991665
Konferens
14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003
Tillgänglig från: 2025-08-25 Skapad: 2025-08-25 Senast uppdaterad: 2026-02-17Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Nilsson, Bengt J.Persson, Mia

Sök vidare i DiVA

Av författaren/redaktören
Nilsson, Bengt J.Persson, Mia
Av organisationen
Teknik och samhälle (TS)
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 18 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf