liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
On Flipping the Frechet Distance
Open Univ Israel, Israel.
Queens Coll CUNY, NY USA.
SUNY Stony Brook, NY USA.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
2024 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 86, no 12, p. 3629-3652Article in journal (Refereed) Published
Abstract [en]

The classical and extensively-studied Fr & eacute;chet distance between two curves is defined as an inf max, where the infimum is over all traversals of the curves, and the maximum is over all concurrent positions of the two agents. In this article we investigate a "flipped" Fr & eacute;chet measure defined by a sup min - the supremum is over all traversals of the curves, and the minimum is over all concurrent positions of the two agents. This measure produces a notion of "social distance" between two curves (or general domains), where agents traverse curves while trying to stay as far apart as possible. We first study the flipped Fr & eacute;chet measure between two polygonal curves in one and two dimensions, providing conditional lower bounds and matching algorithms. We then consider this measure on polygons, where it denotes the minimum distance that two agents can maintain while restricted to travel in or on the boundary of the same polygon. We investigate several variants of the problem in this setting, for some of which we provide linear-time algorithms. We draw connections between our proposed flipped Fr & eacute;chet measure and existing related work in computational geometry, hoping that our new measure may spawn investigations akin to those performed for the Fr & eacute;chet distance, and into further interesting problems that arise.

Place, publisher, year, edition, pages
SPRINGER , 2024. Vol. 86, no 12, p. 3629-3652
Keywords [en]
Social distancing; Fr & eacute;chet distance; Conditional lower bounds; Motion planning
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-208044DOI: 10.1007/s00453-024-01267-8ISI: 001317360400001Scopus ID: 2-s2.0-85204437872OAI: oai:DiVA.org:liu-208044DiVA, id: diva2:1903554
Note

Funding Agencies|NSF [CCF 1910873, CRII 1755791]; Swedish Transport Administration; Swedish Research Council; National Science Foundation [CCF-2007275]; ISRAEL SCIENCE FOUNDATION [2135/24]

Available from: 2024-10-04 Created: 2024-10-04 Last updated: 2025-09-23

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Polishchuk, Valentin
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
In the same journal
Algorithmica
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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