Yoshio Okamoto
Yoshio Okamoto has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Gundert
Institut für Theoretische Informatik ETH Zürich CH-8092 Zürich Switzerland
1 shared publication - Heidi Gebauer
Institute of Theoretical Computer Science, ETH Zurich, CH-8092, Switzerland
1 shared publication - Matias Korman
Université Libre de Bruxelles (ULB) Brussels Belgium
1 shared publication - Robin A. Moser
Institute for Theoretical Computer Science Department of Computer Science ETH Zürich 8092 Zürich Switzerland
1 shared publication - Sang Won Bae
Kyonggi Univ, Div Comp Sci & Engn, Suwon, South Korea
1 shared publication
Latest Publications
- Open Access
The Geodesic Diameter of Polygonal Domains
This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as known by Hershberger and Suri. For general polygonal domains with h >= 1, however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time O(n^7.73) or O(n^7 (log n + h)). The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two.
Open AccessThe Geodesic Diameter of Polygonal Domains
This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as known by Hershberger and Suri. For general polygonal domains with h >= 1, however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time O(n^7.73) or O(n^7 (log n + h)). The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two.
- Open Access
Not All Saturated 3-Forests Are Tight
A basic statement in graph theory is that every inclusion-maximal forest is connected, i.e. a tree. Using a definiton for higher dimensional forests by Graham and Lovasz and the connectivity-related notion of tightness for hypergraphs introduced by Arocha, Bracho and Neumann-Lara in, we provide an example of a saturated, i.e. inclusion-maximal 3-forest that is not tight. This resolves an open problem posed by Strausz.
Open AccessNot All Saturated 3-Forests Are Tight
A basic statement in graph theory is that every inclusion-maximal forest is connected, i.e. a tree. Using a definiton for higher dimensional forests by Graham and Lovasz and the connectivity-related notion of tightness for hypergraphs introduced by Arocha, Bracho and Neumann-Lara in, we provide an example of a saturated, i.e. inclusion-maximal 3-forest that is not tight. This resolves an open problem posed by Strausz.