Search

A well-known theorem in plane geometry states that any set of n non-collinear points in the plane determines at least n lines. Chen and Chvátal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of betweenness. In this paper, we prove that in the plane with the L 1 (also called Manhattan) metric, a non-collinear set of n points induces at least ⌈ n / 2 ⌉ lines. This is an improvement of the previous lower bound of n/37, with substantially different proof. As a consequence, we also get the same lower bound for non-collinear point sets in the plane with the L ∞ metric. [ABSTRACT FROM AUTHOR]

Randomized dimensionality reduction has been recognized as one of the cornerstones in handling high-dimensional data, originating in various foundational works such as the celebrated Johnson-Lindenstrauss Lemma. More specifically, nearest neighbor-preserving embeddings exist for ℓ 2 (Euclidean) and ℓ 1 (Manhattan) metrics, as well as doubling subsets of ℓ 2 , where doubling dimension is today the most effective way of capturing intrinsic dimensionality, as well as input structure in various applications. These randomized embeddings bound the distortion only for distances between the query point and a point set. Motivated by the foundational character of fast Approximate Nearest Neighbor search in ℓ 1 , this paper settles an important missing case, namely that of doubling subsets of ℓ 1. In particular, we introduce a randomized dimensionality reduction by means of a near neighbor-preserving embedding, which is related to the decision-with-witness problem. The input set gets represented with a carefully chosen covering point set; in a second step, the algorithm randomly projects the latter. In order to obtain the covering point sets, we leverage either approximate r -nets or randomly shifted grids, with different tradeoffs between preprocessing time and target dimension. We exploit Cauchy random variables, and derive a concentration bound of independent interest. Our algorithms are rather simple and should therefore be useful in practice. [ABSTRACT FROM AUTHOR]

This study introduces a hybrid Latent Dirichlet Allocation (LDA) model to excavate hidden crash patterns from the large-scale crash dataset. External semantic descriptions have been attached to raw GPS coordinates of crash events. The K-means clustering algorithm is first applied to determine land use characteristics of crash points by grouping surrounding Points of Interests (POIs). Then, each crash record is transformed into a formalized label consisting of land use, Annual Average Daily Traffic (AADT), and time stamps, allowing the analysis of massive traffic crash data as document corpora. Finally, a data-driven modeling approach based on the LDA is conducted to discover hidden crash patterns from traffic crash records combining the external semantic information. The approach is verified using motor vehicle crash data in Manhattan County of New York City. The novel semantic analysis of crash records provides an effective method to investigate the hidden information in traffic crashes. Identifying spatial-temporal patterns on motor vehicle crashes would provide insights into underlying traffic behaviors for intelligent policy-making and resource allocation. [ABSTRACT FROM AUTHOR]

Fuzzy sets that have been presented so far are generally related to one‐coordinate variables. However, some variables are identified by two coordinates, such as a location on a plane. In this case, the membership degree of each point in a fuzzy set is determined by considering the simultaneous values of both coordinates. In this paper, we develop the classical fuzzy set for two‐coordinate variables; we call it the volumetric fuzzy set (VFS) due to the fact that a point on a plane along with its membership degree forms a corresponding point in a three‐dimensional coordinate system. In this study, we present a specific type of VFS in which there is only one ideal point with the highest membership degree, and the membership degrees of other points are inversely correlated with their distances from this ideal point. For this purpose, we apply three types of distances which are Euclidean, Manhattan, and Chebyshev distances. The membership function extracted based on Euclidean distance may have a common volumetric shape, a cone shape, for example, described in detail in this paper; while those extracted based on the other types of distance usually have unusual volumetric shapes. This study also shows the application of the VFS in optimization problems. For this purpose, three location optimization problems are developed based on different types of volumetric membership functions and then solved using the max–min approach. To illustrate the proposed volumetric optimization models, three numerical examples are used and their results are compared. [ABSTRACT FROM AUTHOR]

The grid obstacle representation , or alternately, ℓ 1 -obstacle representation of a graph G = (V , E) is an injective function f : V → Z 2 and a set of point obstacles O on the grid points of Z 2 (where no vertex of V has been mapped) such that u v is an edge in G if and only if there exists a Manhattan path between f (u) and f (v) in Z 2 avoiding the obstacles of O and points in f (V). This work shows that planar graphs admit such a representation while there exist some non-planar graphs that do not admit such a representation. Moreover, we show that every graph admits a grid obstacle representation in Z 3. We also show NP-hardness result for the point set embeddability of an ℓ 1 -obstacle representation. [ABSTRACT FROM AUTHOR]

The p -center problem is finding the location of p facilities among a set of n demand points such that the maximum distance between any demand point and its nearest facility is minimized. In this paper, we study this problem in the context of uncertainty, that is, the location of the demand points may change in a region like a disk or a segment, or belong to a finite set of points. We introduce Max- p -center and Min- p -center problems which are the worst and the best possible solutions for the p -center problem under such locational uncertainty. We propose approximation and parameterized algorithms to solve these problems under the Euclidean metric. Further, we study the MinMax Regret 1-center problem under uncertainty and propose a linear-time algorithm to solve it under the Manhattan metric as well as an O (n 4) time algorithm under the Euclidean metric. [ABSTRACT FROM AUTHOR]