4 Search Results for "Yu, Kiyun"

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.33
Automatic Wall Detection and Building Topology and Property of 2D Floor Plan (Short Paper)

Authors: Hanme Jang, Jong Hyeon Yang, and Yu Kiyun

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

Abstract
Recently, indoor space construction information has been actively carried out primarily in large buildings and in underground facilities. However, the building of this data was done by only a handful of people, and it was a time- and money-intensive task. Therefore, the technology of automatically extracting a wall and constructing a 3D model from architectural floor plans was developed. Complete automation is still limited by accuracy issues, and only a few sets of floor plan data to which the technology can be applied exist. In addition, it is difficult to extract complicated walls and their thickness to build the wall-junction structure of indoor spatial information, which requires significant topological information in the automation process. In this paper, we propose an automatic method of extracting the wall from an architectural floor plan suitable for the restoration of the indoor spatial information according to the indoor spatial information standard.
Cite as

Hanme Jang, Jong Hyeon Yang, and Yu Kiyun. Automatic Wall Detection and Building Topology and Property of 2D Floor Plan (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 33:1-33:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jang_et_al:LIPIcs.GISCIENCE.2018.33,
  author =	{Jang, Hanme and Yang, Jong Hyeon and Kiyun, Yu},
  title =	{{Automatic Wall Detection and Building Topology and Property of 2D Floor Plan}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{33:1--33:5},
  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.33},
  URN =		{urn:nbn:de:0030-drops-93616},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.33},
  annote =	{Keywords: Image Segmentation, Indoor space, Adjacency matrix, Wall thickness}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.39
Application of Style Transfer in the Vectorization Process of Floorplans (Short Paper)

Authors: Seongyong Kim, Seula Park, and Kiyun Yu

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

Abstract
As the market for indoor spatial information burgeons, the construction of indoor spatial databases consequently gain attention. Since floorplans are portable records of buildings, they are an indispensable source for the efficient construction of indoor environments. However, as previous research on floorplan information retrieval usually targeted specific formats, a system for constructing spatial information must include heuristic refinement steps. This study aims to convert diverse floorplans into an integrated format using the style transfer by deep networks. Our deep networks mimic a robust perception of human that recognize the cell structure of floorplans under various formats. The integrated format ensures that unified post-processing steps are required to the vectorization of floorplans. Through this process, indoor spatial information is constructed in a pragmatic way, using a plethora of architectural floorplans.
Cite as

Seongyong Kim, Seula Park, and Kiyun Yu. Application of Style Transfer in the Vectorization Process of Floorplans (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 39:1-39:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.GISCIENCE.2018.39,
  author =	{Kim, Seongyong and Park, Seula and Yu, Kiyun},
  title =	{{Application of Style Transfer in the Vectorization Process of Floorplans}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{39:1--39: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.39},
  URN =		{urn:nbn:de:0030-drops-93672},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.39},
  annote =	{Keywords: Floorplan, Vectorising, Style Transfer, Generative Adversarial Networks}
}
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
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 3 2018

  • Refine by Author
  • 2 Yu, Kiyun
  • 1 Jang, Hanme
  • 1 Kim, Jiyoung
  • 1 Kim, Seongyong
  • 1 Kiyun, Yu
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 1 Applied computing → Graphics recognition and interpretation
  • 1 Computing methodologies → Image segmentation
  • 1 Computing methodologies → Scene understanding
  • 1 Information systems → Content analysis and feature selection
  • 1 Information systems → Information extraction
  • Show More...

  • Refine by Keyword
  • 1 Adjacency matrix
  • 1 Floorplan
  • 1 Fréchet distance
  • 1 Generative Adversarial Networks
  • 1 Geo-Tagging
  • 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