The Experts below are selected from a list of 306 Experts worldwide ranked by ideXlab platform
Sven Schuierer - One of the best experts on this subject based on the ideXlab platform.
-
AN OPTIMAL DATA STRUCTURE FOR SHORTEST Rectilinear PATH QUERIES IN A SIMPLE Rectilinear POLYGON
International Journal of Computational Geometry and Applications, 1996Co-Authors: Sven SchuiererAbstract:We present a data structure that allows to preprocess a Rectilinear polygon with n vertices such that, for any two query points, the shortest path in the Rectilinear link or L1-metric can be reported in time O(log n+k) where k is the link length of the shortest path. If only the distance is of interest, the query time reduces to O(log n). Furthermore, if the query points are two vertices, the distance can be reported in time O(1) and a shortest path can be constructed in time O(1+k). The data structure can be computed in time O(n) and needs O(n) storage. As an application we present a linear time algorithm to compute the diameter of a simple Rectilinear polygon w.r.t. the L1-metric.
-
An optimal algorithm for the Rectilinear link center of a Rectilinear polygon
Computational Geometry, 1996Co-Authors: Bengt J. Nilsson, Sven SchuiererAbstract:The problem of finding the link center of a simple polygon has been studied extensively in recent years. $O(n\log n)$ time upper bounds have been given for this problem and that of computing the link diameter for the polygon. We consider the Rectilinear case of this problem and give linear time algorithms to compute the Rectilinear link diamter and the Rectilinear link center of a simple Rectilinear polygon. As a consequence we also obtain a linear time solution for the Rectilinear link radius problem. To our knowledge these are the first optimal algorithms for center and diamter problems of polygons.
-
STACS - Rectilinear Path Queries in a Simple Rectilinear Polygon
Lecture Notes in Computer Science, 1993Co-Authors: Sven SchuiererAbstract:We present a data structure that allows to preprocess a Rectilinear polygon such that shortest path queries in the Rectilinear link or L1 metric for any two points can be answered in time O(log n + k) where it is the length of the shortest path. If only the distance is of interest, the query time reduces to O(log n). Furthermore, if the query points are two vertices the distance can be reported in time O(1) and ashortest path can be constructed in time O(1 + k). The data structure can be computed in time O(n) and needs O(n) storage.
Haitao Wang - One of the best experts on this subject based on the ideXlab platform.
-
Bicriteria Rectilinear Shortest Paths Among Rectilinear Obstacles in the Plane
Discrete & Computational Geometry, 2019Co-Authors: Haitao WangAbstract:Given a Rectilinear domain \(\mathcal {P}\) of h pairwise-disjoint Rectilinear obstacles with a total of n vertices in the plane, we study the problem of computing bicriteria Rectilinear shortest paths between two points s and t in \(\mathcal {P}\). Three types of bicriteria Rectilinear paths are considered: minimum-link shortest paths, shortest minimum-link paths, and minimum-cost paths where the cost of a path is a non-decreasing function of both the number of edges and the length of the path. The one-point and two-point path queries are also considered. Algorithms for these problems have been given previously. Our contributions are threefold. First, we find a critical error in all previous algorithms. Second, we correct the error in a not-so-trivial way. Third, we further improve the algorithms so that they are even faster than the previous (incorrect) algorithms when h is relatively small. For example, for the minimum-link shortest paths, we obtain the following results. Our algorithm computes a minimum-link shortest \(s\)-\(t\) path in \(O(n+h\log ^{3/2} h)\) time. For the one-point queries, we build a data structure of size \(O(n+ h\log h)\) in \(O(n+h\log ^{3/2} h)\) time for a source point s, such that given any query point t, a minimum-link shortest \(s\)-\(t\) path can be computed in \(O(\log n)\) time. For the two-point queries, with \(O(n+h^2\log ^2 h)\) time and space preprocessing, a minimum-link shortest \(s\)-\(t\) path can be computed in \(O(\log n+\log ^2 h)\) time for any two query points s and t; alternatively, with \(O(n+h^2\cdot \log ^{2} h \cdot 4^{\sqrt{\log h}})\) time and \(O(n+h^2\cdot \log h \cdot 4^{\sqrt{\log h}})\) space preprocessing, we can answer each two-point query in \(O(\log n)\) time. Note that \(h^2\cdot \log ^{2} h \cdot 4^{\sqrt{\log h}}=O(h^{2+\epsilon })\) for any \(\epsilon >0\). These results are particularly interesting when h is relatively small. For example, if \(h=O(n^{1/2-\epsilon })\) for any \(\epsilon >0\), then all above results match the best results for the problems in simple Rectilinear polygons, which are optimal. The complexities for the other two types of paths are slightly worse, but still linearly depend on n (in addition to g(h) for some functions g(h) of h).
-
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains
Algorithmica, 2018Co-Authors: Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski, Haitao WangAbstract:We present a new algorithm for finding minimum-link Rectilinear paths among h Rectilinear obstacles with a total of n vertices in the plane. After the plane is triangulated, for any point s, our algorithm builds an O(n)-size data structure in \(O(n+h\log h)\) time, such that given any query point t, we can compute a minimum-link Rectilinear path from s to t in \(O(\log n+k)\) time, where k is the number of edges of the path, and the query time is \(O(\log n)\) if we only want to know the value k. The previously best algorithm solves the problem in \(O(n\log n)\) time.
-
Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane
arXiv: Computational Geometry, 2017Co-Authors: Haitao WangAbstract:Given a Rectilinear domain $\mathcal{P}$ of $h$ pairwise-disjoint Rectilinear obstacles with a total of $n$ vertices in the plane, we study the problem of computing bicriteria Rectilinear shortest paths between two points $s$ and $t$ in $\mathcal{P}$. Three types of bicriteria Rectilinear paths are considered: minimum-link shortest paths, shortest minimum-link paths, and minimum-cost paths where the cost of a path is a non-decreasing function of both the number of edges and the length of the path. The one-point and two-point path queries are also considered. Algorithms for these problems have been given previously. Our contributions are threefold. First, we find a critical error in all previous algorithms. Second, we correct the error in a not-so-trivial way. Third, we further improve the algorithms so that they are even faster than the previous (incorrect) algorithms when $h$ is relatively small. For example, for the minimum-link shortest paths, we obtain the following results. Our algorithm computes a minimum-link shortest $s$-$t$ path in $O(n+h\log^{3/2} h)$ time. For the one-point queries, we build a data structure of size $O(n+ h\log h)$ in $O(n+h\log^{3/2} h)$ time for a source point $s$, such that given any query point $t$, a minimum-link shortest $s$-$t$ path can be determined in $O(\log n)$ time. For the two-point queries, with $O(n+h^2\log^2 h)$ time and space preprocessing, a minimum-link shortest $s$-$t$ path can be determined in $O(\log n+\log^2 h)$ time for any two query points $s$ and $t$; alternatively, with $O(n+h^2\cdot \log^{2} h \cdot 4^{\sqrt{\log h}})$ time and $O(n+h^2\cdot \log h \cdot 4^{\sqrt{\log h}})$ space preprocessing, we can answer each two-point query in $O(\log n)$ time.
-
Symposium on Computational Geometry - Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane
2017Co-Authors: Haitao WangAbstract:Given a Rectilinear domain P of h pairwise-disjoint Rectilinear obstacles with a total of n vertices in the plane, we study the problem of computing bicriteria Rectilinear shortest paths between two points s and t in P. Three types of bicriteria Rectilinear paths are considered: minimum-link shortest paths, shortest minimum-link paths, and minimum-cost paths where the cost of a path is a non-decreasing function of both the number of edges and the length of the path. The one-point and two-point path queries are also considered. Algorithms for these problems have been given previously. Our contributions are threefold. First, we find a critical error in all previous algorithms. Second, we correct the error in a not-so-trivial way. Third, we further improve the algorithms so that they are even faster than the previous (incorrect) algorithms when h is relatively small. For example, for computing a minimum-link shortest s-t path, the previous algorithm runs in O(n log^{3/2} n) time while the time of our new algorithm is O(n + h log^{3/2} h).
-
Computing the Rectilinear Center of Uncertain Points in the Plane
arXiv: Computational Geometry, 2015Co-Authors: Haitao Wang, Jingru ZhangAbstract:In this paper, we consider the Rectilinear one-center problem on uncertain points in the plane. In this problem, we are given a set $P$ of $n$ (weighted) uncertain points in the plane and each uncertain point has $m$ possible locations each associated with a probability for the point appearing at that location. The goal is to find a point $q^*$ in the plane which minimizes the maximum expected Rectilinear distance from $q^*$ to all uncertain points of $P$, and $q^*$ is called a Rectilinear center. We present an algorithm that solves the problem in $O(mn)$ time. Since the input size of the problem is $\Theta(mn)$, our algorithm is optimal.
Gila Morgenstern - One of the best experts on this subject based on the ideXlab platform.
-
Settling the bound on the Rectilinear link radius of a simple Rectilinear polygon
Information Processing Letters, 2011Co-Authors: Matthew J. Katz, Gila MorgensternAbstract:We improve the best known bound on the Rectilinear link radius of a simple Rectilinear polygon with respect to its Rectilinear link diameter. The new bound is tight and is compatible with the known bound on the (regular) link radius of a (regular) simple polygon with respect to its (regular) link diameter. The previous bound on the Rectilinear link radius of a simple Rectilinear polygon was proven by Nilsson and Schuierer in 1991. Research highlights? We study properties of the Rectilinear link distance in Rectilinear polygons. ? We study the connection between the Rectilinear link radius and diameter. ? We improve the previous upper bound on the Rectilinear link radius. ? We prove a tight upper bound on the Rectilinear link radius.
Mark De Berg - One of the best experts on this subject based on the ideXlab platform.
-
On Rectilinear duals for vertex-weighted plane graphs
Discrete Mathematics, 2009Co-Authors: Mark De Berg, Elena Mumford, Bettina SpeckmannAbstract:Let G=(V,E) be a plane triangulated graph where each vertex is assigned a positive weight. A Rectilinear dual of G is a partition of a rectangle into |V| simple Rectilinear regions, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge in E. A Rectilinear dual is called a cartogram if the area of each region is equal to the weight of the corresponding vertex. We show that every vertex-weighted plane triangulated graph G admits a cartogram of constant complexity, that is, a cartogram where the number of vertices of each region is constant. Furthermore, such a Rectilinear cartogram can be constructed in O(nlogn) time where n=|V|.
-
Rectilinear decompositions with low stabbing number
Information Processing Letters, 1994Co-Authors: Mark De Berg, Marc Van KreveldAbstract:Abstract Let be a Rectilinear polygon. The stabbing number of a decomposition of into rectangles is the maximum number of rectangles intersected by any axis-parallel segment that lies completely inside . We prove that any simple Rectilinear polygon with n vertices admits a decomposition with stabbing number O(logn), and we give an example of a simple Rectilinear polygon for which any decomposition has stabbing number Ω ( log n) . We also show that any Rectilinear polygon with k ⩾ 1 Rectilinear holes and n vertices in total admits a decomposition with stabbing number O(√k logn). When the holes are rectangles, then a decomposition exists with stabbing number O(√k+logn), which we show is tight. All of these decompositions consist of O(n) rectangles.
-
On Rectilinear link distance
Computational Geometry, 1991Co-Authors: Mark De BergAbstract:In this paper we study two link distance problems for Rectilinear paths inside a simple Rectilinear polygon P.First, we present a data structure using O(n log n) storage such that a shortest path between two query points can be computed efficiently. If both query points are vertices of P, the query time is O(1 + l), where l is the number of links. If the query points are arbitrary points inside P, then the query time becomes O(log n + l). The resulting path is not only optimal in the Rectilinear link metric, but it is optimal in the L1-metric as well. Secondly, it is shown that the Rectilinear link diameter of P can be computed in time O(n log n). We also give an approximation algorithm that runs in linear time. This algorithm produces a solution that differs by at most three links from the exact diameter.The solutions are based on a Rectilinear version of Chazelle's polygon cutting theorem. This new theorem states that any simple Rectilinear polygon can be cut into two Rectilinear subpolygons of size at most 34 times the original size, and that such a cut segment can be found in linear time.
Matthew J. Katz - One of the best experts on this subject based on the ideXlab platform.
-
Settling the bound on the Rectilinear link radius of a simple Rectilinear polygon
Information Processing Letters, 2011Co-Authors: Matthew J. Katz, Gila MorgensternAbstract:We improve the best known bound on the Rectilinear link radius of a simple Rectilinear polygon with respect to its Rectilinear link diameter. The new bound is tight and is compatible with the known bound on the (regular) link radius of a (regular) simple polygon with respect to its (regular) link diameter. The previous bound on the Rectilinear link radius of a simple Rectilinear polygon was proven by Nilsson and Schuierer in 1991. Research highlights? We study properties of the Rectilinear link distance in Rectilinear polygons. ? We study the connection between the Rectilinear link radius and diameter. ? We improve the previous upper bound on the Rectilinear link radius. ? We prove a tight upper bound on the Rectilinear link radius.
