Sang Won Bae

activity

20132018

most cited

L_{1}

Shortest Path Queries in Simple Polygons

1 citations · 2 across the 3 of their papers we have counts for

collaborators

Showing cs.CGShow all

3 papers · 1 filter

cs.CG2018★ 1 cited

$L_{1}$ Shortest Path Queries in Simple Polygons

Sang Won Bae, Haitao Wang

Let $P$ be a simple polygon of $n$ vertices. We consider two-point $L_{1}$ shortest path queries in $P$ . We build a data structure of $O (n)$ size in $O (n)$ time such that given any t…

cs.CG2015★ 1 cited

Computing the $L_{1}$ Geodesic Diameter and Center of a Polygonal Domain

Sang Won Bae, Matias Korman, Joseph S. B. Mitchell +3

For a polygonal domain with $h$ holes and a total of $n$ vertices, we present algorithms that compute the $L_{1}$ geodesic diameter in $O (n^{2} + h^{4})$ time and the $L_{1}$ geodesic center…

cs.CG2013

Computing the $L_{1}$ Geodesic Diameter and Center of a Simple Polygon in Linear Time

Sang Won Bae, Matias Korman, Yoshio Okamoto +1

In this paper, we show that the $L_{1}$ geodesic diameter and center of a simple polygon can be computed in linear time. For the purpose, we focus on revealing basic geometric proper…

L1​ Shortest Path Queries in Simple Polygons

Computing the L1​ Geodesic Diameter and Center of a Polygonal Domain

Computing the L1​ Geodesic Diameter and Center of a Simple Polygon in Linear Time

$L_{1}$ Shortest Path Queries in Simple Polygons

Computing the $L_{1}$ Geodesic Diameter and Center of a Polygonal Domain

Computing the $L_{1}$ Geodesic Diameter and Center of a Simple Polygon in Linear Time