2 Search Results for "Kim, Jiyoung"

Document
DOI: 10.4230/LIPIcs.ESA.2025.24
Fréchet Distance in Unweighted Planar Graphs

Authors: Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg, and Lasse Wulf

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The Fréchet distance is a distance measure between trajectories in ℝ^d or walks in a graph G. Given constant-time shortest path queries, the Discrete Fréchet distance D_G(P, Q) between two walks P and Q can be computed in O(|P|⋅|Q|) time using a dynamic program. Driemel, van der Hoog, and Rotenberg [SoCG'22] show that for weighted planar graphs this approach is likely tight, as there can be no strongly-subquadratic algorithm to compute a 1.01-approximation of D_G(P, Q) unless the Orthogonal Vector Hypothesis (OVH) fails. Such quadratic-time conditional lower bounds are common to many Fréchet distance variants. However, they can be circumvented by assuming that the input comes from some well-behaved class: There exist (1+ε)-approximations, both in weighted graphs and in ℝ^d, that take near-linear time for c-packed or κ-straight walks in the graph. In ℝ^d there also exists a near-linear time algorithm to compute the Fréchet distance whenever all input edges are long compared to the distance. We consider computing the Fréchet distance in unweighted planar graphs. We show that there exist no strongly-subquadratic 1.25-approximations of the discrete Fréchet distance between two disjoint simple paths in an unweighted planar graph in strongly subquadratic time, unless OVH fails. This improves the previous lower bound, both in terms of generality and approximation factor. We subsequently show that adding graph structure circumvents this lower bound: If the graph is a regular tiling with unit-weighted edges, then there exists an Õ((|P|+|Q|)^{1.5})-time algorithm to compute D_G(P, Q). Our result has natural implications in the plane, as it allows us to define a new class of well-behaved curves that facilitate (1+ε)-approximations of their discrete Fréchet distance in subquadratic time.
Cite as

Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg, and Lasse Wulf. Fréchet Distance in Unweighted Planar Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.ESA.2025.24,
  author =	{van der Hoog, Ivor and van der Horst, Thijs and Rotenberg, Eva and Wulf, Lasse},
  title =	{{Fr\'{e}chet Distance in Unweighted Planar Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.24},
  URN =		{urn:nbn:de:0030-drops-244924},
  doi =		{10.4230/LIPIcs.ESA.2025.24},
  annote =	{Keywords: Fr\'{e}chet distance, planar graphs, lower bounds, approximation algorithms}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.49
Geotagging Location Information Extracted from Unstructured Data (Short Paper)

Authors: Kyunghyun Min, Jungseok Lee, Kiyun Yu, and Jiyoung Kim

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
Location information is an essential element of location-based services and is used in various ways. Unstructured data contain different types of location information, but coordinate values are required to determine the exact location. In Twitter, a typical social network service (SNS) platform of unstructured data, the number of geotagged tweets is low. If we can estimate the location of text by geotagging a large number of unstructured data, we can estimate the location of the event in real-time. This study is a base study on extracting the location information by using the named entity recognizer provided by the Exobrain API and applying geotagging to unstructured data in Hangul (Korean). We used Chosun news articles, which are grammatically correct and well organized, instead of tweets to extract three location-related categories, namely "location," "organization," and "artifact". We used the named entity recognizer and geotagged each sentence in combination of the fields in each category. The results of the study showed that 61% of the 800 test sentences did not have the location-related information, thus hindering geotagging. In 11.75% of the test sentences, geotagging was possible with only the given location information extracted using the named entity recognizer. The remaining 27.25% of the sentences contained information on more than two locations from the same subcategories and hence required location estimation from candidate locations. In future research, we plan to apply the results of this study to develop location estimation algorithm that makes use of the extracted location-related entities from purely unstructured data such as that on SNSs.
Cite as

Kyunghyun Min, Jungseok Lee, Kiyun Yu, and Jiyoung Kim. Geotagging Location Information Extracted from Unstructured Data (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 49:1-49:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{min_et_al:LIPIcs.GISCIENCE.2018.49,
  author =	{Min, Kyunghyun and Lee, Jungseok and Yu, Kiyun and Kim, Jiyoung},
  title =	{{Geotagging Location Information Extracted from Unstructured Data}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{49:1--49:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.49},
  URN =		{urn:nbn:de:0030-drops-93778},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.49},
  annote =	{Keywords: Location Estimation, Information Extraction, Geo-Tagging, Location Information, Unstructured Data}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2018

  • Refine by Author
  • 1 Kim, Jiyoung
  • 1 Lee, Jungseok
  • 1 Min, Kyunghyun
  • 1 Rotenberg, Eva
  • 1 Wulf, Lasse
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Information systems → Content analysis and feature selection
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Fréchet distance
  • 1 Geo-Tagging
  • 1 Information Extraction
  • 1 Location Estimation
  • 1 Location Information
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact