Search

Identifying Alzheimer’s disease (AD) in its early stages is a challenging task for physicians and clinicians. This paper proposes a new algorithm for diagnosing AD, which is based on analyzing spontaneous speech signals. The proposed method uses two visibility graph methods, Natural Visibility Graph (NVG) and Horizontal Visibility Graph (HVG), to derive features from speech windows. These features are then given to a deep BiLSTM-based classifier to decide about segments of the signal. The proposed approach could obtain a sensitivity of 98.33%, specificity of 99.44%, and accuracy of 99.17%. The advantage of converting speech signals into graphs using NVG and HVG is that it allows for the extraction of complex structural features that are not easily captured by traditional methods. This method is highly beneficial due to its non-invasive nature, low cost, and lack of side effects. Patients can undergo the procedure without experiencing any discomfort, while also benefiting from its affordability and accessibility. The method’s safety and practicality make it an ideal choice for those seeking a reliable and effective solution. Moreover, the proposed algorithm has a high accuracy in detecting the early stage of AD, which makes it a promising tool to evaluate Alzheimer’s disease diagnosis in its pre-clinical stage. [ABSTRACT FROM AUTHOR]

Visibility graphs provide a novel approach for analysing time-series data. Graph theoretical analysis of visibility graphs can provide new features for data mining applications in fMRI. However, visibility graphs features have not been used widely in the field of neuroscience. This is likely due to a lack of understanding of their robustness in the presence of noise (e.g., motion) and their test-retest reliability. In this study, we investigated visibility graph properties of fMRI data in the human connectome project (N = 1010) and tested their sensitivity to motion and test-retest reliability. We also characterised the strength of connectivity obtained using degree synchrony of visibility graphs. We found that strong correlation (r > 0.5) between visibility graph properties, such as the number of communities and average degrees, and motion in the fMRI data. The test-retest reliability (Intraclass correlation coefficient (ICC)) of graph theoretical features was high for the average degrees (0.74, 95% CI = [0.73, 0.75]), and moderate for clustering coefficient (0.43, 95% CI = [0.41, 0.44]) and average path length (0.41, 95% CI = [0.38, 0.44]). Functional connectivity between brain regions was measured by correlating the visibility graph degrees. However, the strength of correlation was found to be moderate to low (r < 0.35). These findings suggest that even small movement in fMRI data can strongly influence robustness and reliability of visibility graph features, thus, requiring robust motion correction strategies prior to data analysis. Further studies are necessary for better understanding of the potential application of visibility graph features in fMRI. [ABSTRACT FROM AUTHOR]

In the face of escalating frequency and severity of hot extreme (HE) events worldwide, understanding their spatio-temporal characteristics and hazard patterns has become crucial. This study employs a complex network (CN) approach, specifically using visibility graph and similarity network analysis, to investigate HEs. According to the HE network, we have successfully identified anomalous years, divided stages of change, selected representative cities, and zoned spatial hazard patterns of HE. Results reveal that 85% of cities in China experienced varying degrees of increasing HEs, with the highest increase observed as 63 times. The HE networks in China exhibit small-world characteristics, allowing the classification of HE changes into 5–8 stages and 10 types. Hefei emerges as the most representative city in this context. Additionally, the hazard of HE in China can be divided into four grades, with a gradual increase from north to south. This study sheds light on the intensifying hot extreme events in China and establishes a connection between CN and HE analysis, offering innovative ideas and methods for studying climate extremes. [ABSTRACT FROM AUTHOR]

We prove that, given a polyhedron P in R 3 , every point in R 3 that does not see any vertex of P must see eight or more edges of P , and this bound is tight. More generally, this remains true if P is any finite arrangement of internally disjoint polygons in R 3 . We also prove that every point in R 3 can see six or more edges of P (possibly only the endpoints of some these edges) and every point in the interior of P can see a positive portion of at least six edges of P . These bounds are also tight. [ABSTRACT FROM AUTHOR]

A rectangle visibility graph (RVG) is represented by assigning to each vertex a rectangle in the plane with horizontal and vertical sides in such a way that edges in the graph correspond to unobstructed horizontal and vertical lines of sight between their corresponding rectangles. To discretize, we consider only rectangles whose corners have integer coordinates. For any given RVG, we seek a representation with smallest bounding box as measured by its area, perimeter, height, or width (height is assumed not to exceed width). We derive a number of results regarding these parameters. Using these results, we show that these four measures are distinct, in the sense that there exist graphs G 1 and G 2 with area (G 1) < area (G 2) but perim (G 2) < perim (G 1) , and analogously for all other pairs of these parameters. We further show that there exists a graph G 3 with representations S 1 and S 2 such that area (G 3) = area (S 1) < area (S 2) but perim (G 3) = perim (S 2) < perim (S 1) . In other words, G 3 requires distinct representations to minimize area and perimeter. Similarly, such graphs exist to demonstrate the independence of all other pairs of these parameters. Among graphs with n ≤ 6 vertices, the empty graph E n requires largest area. But for graphs with n = 7 and n = 8 vertices, we show that the complete graphs K 7 and K 8 require larger area than E 7 and E 8 , respectively. Using this, we show that for all n ≥ 8 , the empty graph E n does not have largest area, perimeter, height, or width among all RVGs on n vertices. [ABSTRACT FROM AUTHOR]

El Niño-Southern Oscillation (ENSO) is a complex climate phenomenon that results from ocean–atmosphere interactions and exhibits nonlinearity in both spatial and temporal evolution. The directed horizontal visibility graph (DHVG) and Kullback–Leibler divergence (KLD) efficiently characterize the nonlinearity of complex systems without requiring additional symbolization processes. Our study utilizes this method to quantify sea surface temperature (SST) irreversibility across multiple El Niño events and identified similar fluctuation patterns. Subsequently, we map the irreversibility series into visibility graphs and analyze multiple topological properties to investigate the fluctuation structure of SST irreversibility. The irreversibility fluctuation structure effectively explains the periodic changes of El Niño and its nonlinear evolution over time. Results show that KLD exhibits a sharp increase during the strengthening and ending phases of El Niño events and remains in a lower value after the peak month of Niño events; the visibility graph of SST irreversibility exhibits scale-free and small-world properties, indicating that the KLD series has scale invariance and self-similarity, and its fluctuations are not random but correlated; Hurst exponent analysis revealed long-range anti-persistence and mean reversion characteristics in the KLD series. This study utilizes complex network and information theory to investigate the fluctuation pattern and structure of SST irreversibility during El Niño events, providing novel insights into the evolution of ENSO over time scales. [ABSTRACT FROM AUTHOR]

During the last decade, there has been a significant increase in the number of newly constructed apartment buildings in Tirana. The new residences are mostly hi-raised multifamily blocks which are replacing the existing low-storey urban fabric. The balance between outdoor and indoor life is rapidly changing because the communal public spaces in Tirana continue to disappear. The quality and efficiency of apartment design, provision of adequate spaces for common activities inside the dwellings have increasingly now started to play a more important role. The Space Syntax visibility analysis helps to understand the difference in the design approach of the apartments from the perspective of different price categories. Matching the visibility graphs with the room function allows for the comparison of the social meaning of space with its design quality and furthermore, to understanding its level of privacy. The results show that there is a similar approach in the design of the apartments at any price level. This uniformity is based on the standard expectations of both the residents and the developers. [ABSTRACT FROM AUTHOR]

We propose a fully unsupervised network-based methodology for estimating Gaussian Mixture Models on financial time series by maximum likelihood using the Expectation-Maximization algorithm. Visibility graph-structured information of observed data is used to initialize the algorithm. The proposed methodology is applied to the US wholesale electricity market. We will demonstrate that encoding time series through Visibility Graphs allows us to capture the behavior of the time series and the nonlinear interactions between observations well. The results reveal that the proposed methodology outperforms more established approaches. [ABSTRACT FROM AUTHOR]

The analysis of time series and images is significant across different fields due to their widespread applications. In the past few decades, many approaches have been developed, including data-driven artificial intelligence methods, mechanism-driven physical methods, and hybrid mechanism and data-driven models. Complex networks have been used to model numerous complex systems due to its characteristics, including time series prediction and image classification. In order to map time series and images into complex networks, many visibility graph algorithms have been developed, such as horizontal visibility graph, limited penetrable visibility graph, multiplex visibility graph, and image visibility graph. The family of visibility graph algorithms will construct different types of complex networks, including (un-) weighted, (un-) directed, and (single-) multi-layered networks, thereby focusing on different kinds of properties. Different types of visibility graph algorithms will be reviewed in this paper. Through exploring the topological structure and information in the network based on statistical physics, the property of time series and images can be discovered. In order to forecast (multivariate) time series, several variations of local random walk algorithms and different information fusion approaches are applied to measure the similarity between nodes in the network. Different forecasting frameworks are also proposed to consider the information in the time series based on the similarity. In order to classify the image, several machine learning models (such as support vector machine and linear discriminant) are used to classify images based on global features, local features, and multiplex features. Through various simulations on a variety of datasets, researchers have found that the visibility graph algorithm outperformed existing algorithms, both in time series prediction and image classification. Clearly, complex networks are closely connected with time series and images by visibility graph algorithms, rendering complex networks to be an important tool for understanding the characteristics of time series and images. Finally, we conclude in the last section with future outlooks for the visibility graph. [ABSTRACT FROM AUTHOR]

Path planning is a key problem to be solved for mobile robot to realize autonomous navigation. It is a typical computing intensive task, and high computing capacity is needed. The computing power carried by the mobile robot is difficult to support the calculation of path planning, and the traditional cloud computing model cannot meet the real-time requirement of path planning. In order to solve the problem of insufficient computing power and improve the execution efficiency and real-time performance, a real-time computing framework based on edge-cloud collaborative computing is constructed for path planning. In each control decision cycle, the mobile robot as the edge acquires the sensing data and transmits it to the cloud. By stream computing, the cloud plans the path in real-time. The edge integrates the planned path from the cloud and the partial obstacle avoidance result from the edge as a path sequence. The final path sequence is sent to the motion control layout, and drives the mobile robot to the target. By the edge-cloud collaborative computing, the computing capability of the edge is extended. By taking use of high real-time performance of stream computing, the proposed algorithm improves the efficiency of path planning. By taking use of the storage capacity of the cloud, environmental memory is realized and the problem of local traps is solved. Simulation experiment results in different environments show that the planned path by the proposed algorithm gets a higher path quality and shorter execution time comparing the other several traditional path planning algorithms. Experiments in real environment verify the feasibility and effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

Optimal path planning on non-convex maps is challenging: sampling-based algorithms (such as RRT) do not provide optimal solution in finite time; approaches based on visibility graphs are computationally expensive, while reduced visibility graphs (e.g., tangent graph) fail on such maps. We leverage a well-established, and surprisingly less utilized in path planning, geometrical property of convex decompositions i.e. a concave shape can be decomposed into multiple convex shapes. We propose a novel local tangent based approach, inspired by such convex decompositions, to path planning in non-convex maps. Although our local tangent approach is inspired by geometric convex decompositions, it does not require complex decomposition process. Our second contribution is an efficient corner detection method which reasons on binary pixel occupancy maps. Combined with our novel local tangent approach, which intelligently selects nodes from these corners, we modify the standard A* algorithm by feeding these nodes to its open list. With our local tangent approach, only small number of selected corners are fed to A* open list which keeps its size small even for larger maps, resulting in lower convergence time. We formally prove the optimality of our solution. Simulation on our own maps and public dataset (MAPF http://mapf.info/) as well as real-world experiments show that our proposed LTA* algorithm gives better convergence time and shorter path length in environments with both convex and concave obstacles. [ABSTRACT FROM AUTHOR]

This study investigates the relationship between the b value of the Gutenberg–Richter law and the so-called k–M slope, a topological parameters, derived from the visibility graph analysis, that recently has been gaining great attention in describing the time dynamics of seismicity. The relationship has been already found to be nearly linear for several seismic areas. In this paper, we investigate such relationship in two of the most seismically active areas of the world: Italy and Taiwan. Our findings indicate that the relationship between the Gutenberg–Richter b value and k–M slope is nearly linear with a slope of regression line of about 0.07. Furthermore, analysing the seismicity by using the directed visibility graph, the role of the aftershocks is evidenced by the value of two new parameters, defined as the difference and the ratio between the forward directed and the backward directed k–M slopes, which are higher for the whole catalogues than for the aftershock-depleted ones. [ABSTRACT FROM AUTHOR]

We propose a navigation model for indoor environments that combines a 3D geometric modeling of buildings with connection properties of spaces and semantic elements such as openings and installations. The model is an extension of the IndoorGML standard navigation module with a twofold benefit: the extension facilitated the data import from the international standard CityGML and introduced the semantics of various fixtures in indoor space of buildings making the navigation model more suitable for human needs. Several experiments have been conducted by extracting networks from CityGML data and performing a comparison with other network construction techniques. The second contribution of the paper is an algorithm for the automatic extraction of the navigation network. Such an algorithm is a hybrid solution between medial axis approaches and visibility graph approaches. Normally, medial axes approaches are a good representation of human navigation in narrow corridors, especially to avoid obstacles, but introduce distortions in open space. On the other hand, visibility approaches work better in open spaces. In our extraction technique, the resulting network takes advantages of both approaches and better mimics human beings' navigation in indoor environments. [ABSTRACT FROM AUTHOR]

Conventionally invariant mass or transverse momentum techniques have been used to probe for any formation of some exotic or unusual resonance states in high energy collision. In this work, we have applied symmetry scaling based complex network approach to study exotic resonance/hadronic states utilizing the clustering coefficients and associated scaling parameter extracted with the complex network based technique of Visibility Graph. We have analyzed the data of Pb–Pb collision data sample at 2.76 TeV from ALICE Collaboration and analyzed different patterns of symmetry scaling, scale-freeness, correlation and clustering among the produced particles. This is a chaos-based complex network technique where simple parameters like Average Clustering Coefficient and Power of Scale-freeness of Visibility Graph (PSVG) may hint at formation of some exotic or unusual resonance states without using conventional methods. From this experiment we may infer that highest range of Average clustering coefficient, might be the resonance states/clusters from where the hadronic decay might have occurred and few clusters with highest value of this parameter may indicate that those clusters may be the ancestors of some strange particles. There have also been extensive study of dilepton production since the study of lepton pair generation in Drell–Yan processes is immensely important as these processes enable us to validate the Standard Model-SM predictions for the fundamental particles interaction at the new energy region and also to probe for new physics beyond SM. Hence we have applied the same methodology and extracted the same parameters for p–p collision data at 8 TeV from CMS, to detect possible resonance states eventually generating lepton pairs. [ABSTRACT FROM AUTHOR]

Let P be a finite set of points in the plane and S a set of non-crossing line segments with endpoints in P. The visibility graph of P with respect to S, denoted Vis (P , S) , has vertex set P and an edge for each pair of vertices u, v in P for which no line segment of S properly intersects uv. We show that the constrained half- θ 6 -graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of Vis (P , S) . We then show how to construct a plane 6-spanner of Vis (P , S) with maximum degree 6 + c , where c is the maximum number of segments of S incident to a vertex. [ABSTRACT FROM AUTHOR]

The study of sleep has continued to garner increased attention. However, most studies assume stationarity of sleep electroencephalogram (EEG) signals, whereas they are typically nonlinear and nonstationary. Little work has focused on the time irreversibility of sleep EEG signals. Hence, the aim of this work is to reveal the temporally irreversible structures of rapid-eye-movement (REM) and non-REM sleep using a visibility algorithm, which is robust to nonstationarity and finite-size effect. Results show that the temporal structure of non-REM sleep is more irreversible than that of REM sleep. The degree of irreversibility is highest in slow-wave sleep. Moreover, statistical analysis suggests that aging is the major factor that affects the irreversibility of sleep signals, while gender and body mass index contribute insignificantly. The dominant role of slow oscillations on the irreversible structures of the sleep signals is also indicated. [ABSTRACT FROM AUTHOR]

In the dynamics analysis of heart rate, the complexity of visibility graphs (VGs) is seen as a sign of short term variability in signals. The present study was conducted to investigate the possible impact of meditation on heart rate signals complexity using VG method. In this study, existing heart rate signals in Physionet database were used. The dynamics of the signals were then studied both before and during meditation by examining the complexity of VGs using graph index complexity (GIC). Generally, the obtained results showed that the heart rate signals were more complex during meditation. The simple process of calculating the GIC of VG and its adaptability to the chaotic nature of the biological signals can help in estimating the heart rate complexity in meditation. [ABSTRACT FROM AUTHOR]

In the present paper, a novel graph-based approach to the shape decomposition problem is addressed. The shape is appropriately transformed into a visibility graph enriched with local neighborhood information. A two-step diffusion process is then applied to the visibility graph that efficiently enhances the information provided, thus leading to a more robust and meaningful graph construction. Inspired by the notion of a clique as a strict cluster definition, the dominant sets algorithm is invoked, slightly modified to comport with the specific problem of defining shape parts. The cluster cohesiveness and a node participation vector are two important outputs of the proposed graph partitioning method. Opposed to most of the existing techniques, the final number of the clusters is determined automatically, by estimating the cluster cohesiveness on a random network generation process. Experimental results on several shape databases show the effectiveness of our framework for graph-based shape decomposition. [ABSTRACT FROM AUTHOR]

Carbon emissions drive climate change. Especially with the rapid development of economy, carbon emissions are increasing in recent years, and the carbon emission data sets are more comprehensive. How to analyze the data is important. Furthermore, to find the main characteristics of carbon emission, we propose a new method of segmentation in the time series that adopts communities finding in complex network, graph convolution networks (GCN) and visibility graph (VG). Experiments on carbon emission datasets show that the detector has better detection performance than existing graph connectivity-based detectors. In addition, we find that combining the results of GCN segmentation can highlight economic geographic attributes such as resource endowment, industrial structure, and market demand in carbon emission regions, thus complementing the existing applications of complex network methods in the energy field and providing insights for decision support of carbon emissions. [ABSTRACT FROM AUTHOR]

We present an analysis of the seismicity of northern Iran in the period between 2005 and 2016 using a recently introduced method based on concepts of graph theory. The method relies on the inter-event visibility defined in terms of a connectivity degree parameter, k, which is correlated with the earthquake magnitude, M. Previous studies show that the slope m of the line fitting the k- M plot by the least squares method also observes a relationship with the b value from the Gutenberg-Richter law, thus rendering the graph analysis useful to examine the seismicity of a region. These correlations seem to hold for the analysis of relatively small sequences of earthquakes, offering the possibility of studying seismicity parameters in time. We apply this approach to the case of the seismicity of northern Iran, using an earthquake catalog for the tectonic seismic regions of Azerbaijan, Alborz, and Kopeh Dagh. We use results drawn for this region with the visibility graph approach in combination with results from other similar studies to further improve the universal relationship between m and b, and show that the visibility graph approach can be considered as a valid alternative for analyzing regional seismicity properties and earthquake sequences. [ABSTRACT FROM AUTHOR]

This paper introduces a fast algorithm that finds collision-free 3D paths for unmanned aircraft in urban environments. These environments are represented by a three-dimensional scenario in which obstacles are vertical polyhedra. This algorithm uses a method to reduce the number of obstacles taken into account in the path finding process. This method is combined with an algorithm that computes approximate Euclidean shortest paths, which has been adapted to suit this kind of scenarios. Instead of focusing on reducing the asymptotic worst-case running time of the algorithm in unrealistic cases, this approach aims to reduce the computation time in a more practical situation. Experimental cases are provided comparing our approach to existing methods in the literature, showing it is very competitive both in terms of speed and solution quality. [ABSTRACT FROM AUTHOR]

Path planning constitutes one of the most crucial abilities an autonomous robot should possess, apart from Simultaneous Localization and Mapping algorithms (SLAM) and navigation modules. Path planning is the capability to construct safe and collision free paths from a point of interest to another. Many different approaches exist, which are tightly dependent on the map representation method (metric or feature-based). In this work four path planning algorithmic families are described, that can be applied on metric Occupancy Grid Maps (OGMs): Probabilistic RoadMaps (PRMs), Visibility Graphs (VGs), Rapidly exploring Random Trees (RRTs) and Space Skeletonization. The contribution of this work includes the definition of metrics for path planning benchmarks, actual benchmarks of the most common global path planning algorithms and an educated algorithm parameterization based on a global obstacle density coefficient. [ABSTRACT FROM AUTHOR]

This paper addresses the NP-complete problem of Navigation Among Movable Obstacles (NAMO) in which a robot is required to find a collision-free path toward a goal through manipulating and transferring some movable objects on its way. The robot's main goal is to optimize a performance criterion such as runtime, length of transit or transfer paths, number of manipulated obstacles, total number of displacements of all objects, etc. We have designed a recursive algorithm capable of solving various NAMO problems, ranging from linear monotone to nonlinear non-monotone, and with convex or concave polygonal obstacles. Through the adopted approach, the original problem is decomposed into recursively-solved subproblems, in each of which only one movable object is manipulated. In each call of the algorithm, first a Visibility Graph determines a path from the robot's current configuration to an intermediate goal configuration, and then a tentative final configuration for the last object intercepting the path is calculated using the Penetration Depth concept. It is assumed that the objects can be pulled or pushed, but not rotated, in a continuous space, and under such assumptions the method is complete and locally optimal for convex objects, with a worst-case time complexity of O( n 3) in which m is the number of movable objects and n is the number of all vertices on them. Several computational experiments showed that compared to the existing methods in the literature, the proposed recursive method achieved equal or smaller number of transferred obstacles or the total number of displacements of all objects in majority of the test problems. [ABSTRACT FROM AUTHOR]

A visibility graph (VG) is a rather novel statistical method in earthquake sequence analysis; it maps a time series into networks or graphs, converting dynamical properties of the time series into topological properties of networks. By using the VG approach, we defined the parameter window mean interval connectivity time < T>, that informs about the mean linkage time between earthquakes. We analysed the time variation of < T> in the aftershock-depleted catalogue of Kachchh Gujarat (Western India) seismicity from 2003 to 2012, and we found that < T>: i) changes through time, indicating that the topological properties of the earthquake network are not stationary; and, ii) appeared to significantly decrease before the largest shock (M5.7) that occurred on March 7, 2006 near the Gedi fault, an active fault in the Kachchh region. [ABSTRACT FROM AUTHOR]

For natural group movement of non player characters (NPCs) in a computer game, an efficient planning algorithm is necessary. This paper presents a grid window-based path planning algorithm for realistic group movement. The global path is planned in a static environment and the path is locally repaired to avoid dynamic obstacles during execution. The planning and execution processes are performed for the group, not for individual NPCs by using a 2D virtual grid window covering all the NPCs. The movement of each NPC is generated inside the grid window without complicated procedures to detect collisions. We implement and test the algorithm on a polygonal world modeling a real game background. The simulation results show that the proposed method provides natural group movement and dynamic obstacle avoidance, and the experimental result with various numbers of NPCs shows consistent performance. [ABSTRACT FROM AUTHOR]

Functional brain network, one of the main methods for brain functional studies, can provide the connectivity information among brain regions. In this research, EEG-based functional brain network is built and analyzed through a new wavelet limited penetrable visibility graph (WLPVG) approach. This approach first decompose EEG into δ, θ, α, β sub-bands, then extracting nonlinear features from single channel signal, in addition forming a functional brain network for each sub-band. Manual acupuncture (MA) as a stimulation to the human nerve system, may evoke varied modulating effects in brain activities. To investigating whether and how this happens, WLPVG approach is used to analyze the EEGs of 15 healthy subjects with MA at acupoint ST36 on the right leg. It is found that MA can influence the complexity of EEG sub-bands in different ways and lead the functional brain networks to obtain higher efficiency and stronger small-world property compared with pre-acupuncture control state. [ABSTRACT FROM AUTHOR]

We address the problem of repeated coverage of a target area, of any polygonal shape, by a team of robots having a limited visual range. Three distributed Cluster-based algorithms, and a method called Cyclic Coverage are introduced for the problem. The goal is to evaluate the performance of the repeated coverage algorithms under the effects of the variables: Environment Representation, and the Robots' Visual Range. A comprehensive set of performance metrics are considered, including the distance the robots travel, the frequency of visiting points in the target area, and the degree of balance in workload distribution among the robots. The Cyclic Coverage approach, used as a benchmark to compare the algorithms, produces optimal or near-optimal solutions for the single robot case under some criteria. The results can be used as a framework for choosing an appropriate combination of repeated coverage algorithm, environment representation, and the robots' visual range based on the particular scenario and the metric to be optimized. [ABSTRACT FROM AUTHOR]

We consider the problem of mapping an initially unknown polygon of size n with a simple robot that moves inside the polygon along straight lines between the vertices. The robot sees distant vertices in counter-clockwise order and is able to recognize the vertex among them which it came from in its last move, i.e. the robot can look back. Other than that the robot has no means of distinguishing distant vertices. We assume that an upper bound on n is known to the robot beforehand and show that it can always uniquely reconstruct the visibility graph of the polygon. Additionally, we show that multiple identical and deterministic robots can always solve the weak rendezvous problem in which the robots need to position themselves such that all of them are mutually visible to each other. Our results are tight in the sense that the strong rendezvous problem, where robots need to gather at a vertex, cannot be solved in general, and, without knowing a bound beforehand, not even n can be determined. In terms of mobile agents exploring a graph, our result implies that they can reconstruct any graph that is the visibility graph of a simple polygon. This is in contrast to the known result that the reconstruction of arbitrary graphs is impossible in general, even if n is known. [ABSTRACT FROM AUTHOR]

Let s be a point source of light inside a polygon P of n vertices. A polygonal path from s to some point t inside P is called a diffuse reflection path if the turning points of the path lie on edges of P. A diffuse reflection path is said to be optimal if it has the minimum number of reflections on the path. The problem of computing a diffuse reflection path from s to t inside P has not been considered explicitly in the past. We present three different algorithms for this problem which produce suboptimal paths. For constructing such a path, the first algorithm uses a greedy method, the second algorithm uses a transformation of a minimum link path, and the third algorithm uses the edge-edge visibility graph of P. The first two algorithms are for polygons without holes, and they run in O( n+ klog n) time, where k denotes the number of reflections in the constructed path. The third algorithm is for polygons with or without holes, and it runs in O( n) time. The number of reflections in the path produced by this third algorithm can be at most three times that of an optimal diffuse reflection path. Though the combinatorial approach used in the third algorithm gives a better bound on the number of reflections on the path, the first and the second algorithms stand on the merit of their elegant geometric approaches based on local geometric information. [ABSTRACT FROM AUTHOR]

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesník (Acta Fac. Rerum Nat. Univ. Comen. Math. 30:71-93, ) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesník by showing that for any two vertices v and w in a graph of diameter 2, if deg( v)≤deg( w) then there exist deg( v) edge-disjoint vw-paths of length at most 4. For vertex-connectivity, we prove that every visibility graph with n vertices and at most ℓ collinear vertices has connectivity at least $\frac{n-1}{\ell-1}$, which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that ℓ=4 we improve this bound to two thirds of the minimum degree. [ABSTRACT FROM AUTHOR]

The obstacle number of a graph G is the smallest number of polygonal obstacles in the plane with the property that the vertices of G can be represented by distinct points such that two of them see each other if and only if the corresponding vertices are joined by an edge. We list three small graphs that require more than one obstacle. Using extremal graph theoretic tools developed by Prömel, Steger, Bollobás, Thomason, and others, we deduce that for any fixed integer h, the total number of graphs on n vertices with obstacle number at most h is at most $${2^{o(n^2)}}$$. This implies that there are bipartite graphs with arbitrarily large obstacle number, which answers a question of Alpert et al. (Discret Comput Geom doi:, ). [ABSTRACT FROM AUTHOR]

There are several works that approach the modeling of navigation environments for the automatic planning of paths for Unmanned Aerial Vehicles (UAVs). However these works do not consider the evaluation of risks to the population in case of accidents with UAVs. The present work proposes a grid-based method to construct visibility graphs based on the evaluation of effects of impacts of UAVs on the ground and on a set of geographic information. The metric used for the evaluation is the minimum acceptable period between accidents of this type. The geographic information to be used consists of georeferenced images and digital elevation models of the surfaces of the navigation environments; urban and rural population density information of the cities in these environments; and the polygonal representation of the cities. The visibility graphs constructed by the proposed method allow the UAVs to plan the shortest paths with a decrease of the probability of fatalities due to accidents with impact of UAVs on the ground. Analyses of the results are presented in this work. [ABSTRACT FROM AUTHOR]

new chaos–wavelet approach is presented for electroencephalogram (EEG)-based diagnosis of Alzheimer’s disease (AD) employing a recently developed concept in graph theory, visibility graph (VG). The approach is based on the research ideology that nonlinear features may not reveal differences between AD and control group in the band-limited EEG, but may represent noticeable differences in certain sub-bands. Hence, complexity of EEGs is computed using the VGs of EEGs and EEG sub-bands produced by wavelet decomposition. Two methods are employed for computation of complexity of the VGs: one based on the power of scale-freeness of a graph structure and the other based on the maximum eigenvalue of the adjacency matrix of a graph. Analysis of variation is used for feature selection. Two classifiers are applied to the selected features to distinguish AD and control EEGs: a Radial Basis Function Neural Network (RBFNN) and a two-stage classifier consisting of Principal Component Analysis (PCA) and the RBFNN. After comprehensive statistical studies, effective classification features and mathematical markers were discovered. Finally, using the discovered features and a two-stage classifier (PCA-RBFNN), a high diagnostic accuracy of 97.7% was obtained. [ABSTRACT FROM AUTHOR]

An obstacle representation of a graph G is a drawing of G in the plane with straight-line edges, together with a set of polygons (respectively, convex polygons) called obstacles, such that an edge exists in G if and only if it does not intersect an obstacle. The obstacle number (convex obstacle number) of G is the smallest number of obstacles (convex obstacles) in any obstacle representation of G. In this paper, we identify families of graphs with obstacle number 1 and construct graphs with arbitrarily large obstacle number (convex obstacle number). We prove that a graph has an obstacle representation with a single convex k-gon if and only if it is a circular arc graph with clique covering number at most k in which no two arcs cover the host circle. We also prove independently that a graph has an obstacle representation with a single segment obstacle if and only if it is the complement of an interval bigraph. [ABSTRACT FROM AUTHOR]

Suppose S⊆ℝ d is a set of (finite) cardinality n, whose complement can be written as the union of k convex sets. It is perhaps intuitively appealing that when n is large k must also be large. This is true, as is shown here. First the case in which the convex sets must also be open is considered, and in this case a family of examples yields an upper bound, while a simple application of a theorem of Björner and Kalai yields a lower bound. Much cruder estimates are then obtained when the openness restriction is dropped. For a given set S the problem of determining the smallest number of convex sets whose union is ℝ d∖ S is shown to be equivalent to the problem of finding the chromatic number of a certain (infinite) hypergraph ℋ S. We consider the graph $\mathcal {G}_{S}$ whose edges are the 2-element edges of ℋ S, and we show that, when d=2, for any sufficiently large set S, the chromatic number of $\mathcal{G}_{S}$ will be large, even though there exist arbitrarily large finite sets S for which $\mathcal{G}_{S}$ does not contain large cliques. [ABSTRACT FROM AUTHOR]

This paper presents an efficient approach to represent the environment, which can be used to facilitate dynamic path planning in robot navigation systems. The environment is modelled by first defining a 'virtual rectangle' to represent an environment that avoids unwanted obstacles. The obstacles within the environment are then represented as convex polygons to generate the required visibility graph. The devised techniques lend well for hardware porting and thus highly suited to high-speed generation of the visibility graph. It has been demonstrated that efficient dynamic path planning can be realised by generating the 'virtual rectangle' on the fly such that only the environment needed to facilitate onward traversal can be identified. Finally, the proposed algorithms lend well for high-speed computations as they facilitate a high-degree of parallelism at the architecture level. [ABSTRACT FROM AUTHOR]

A path planning algorithm for a mobile robot subject to nonholonomic constraints is presented. The algorithmemploys a global- local strategy, and solves the problem in the 2D workspace of the robot, without generating the complexconfiguration space. Firstly, a visibility graph is constructed for finding a collision-free shortest path for a point. Secondly,the path for a point is evaluated to find whether it can be used as a reference to build up a feasible path for the mobile robot.If not, this path is discarded and the next shortest path is selected and evaluated until a right reference path is found. Thirdly,robot configurations are placed along the selected path in the way that the robot can move from one configuration to the nextavoiding obstacles. Lemmas are introduced to ensure that the robot travels using direct, indirect or reversal manoeuvres. Thealgorithm is computationally efficient and runs in time O(nk + n log n) for k obstacles andn vertices. The path found is near optimal in terms of distance travelled. The algorithm is tested in computersimulations and test results are presented to demonstrate its versatility in complex environments. [ABSTRACT FROM AUTHOR]

A funnel, which is notable for its fundamental role in visibility algorithms, is defined as a polygon that has exactly three convex vertices, two of which are connected by a boundary edge. In this paper we investigate the visibility graph of a funnel which we call an F-graph. We first present two characterizations of an F-graph, one of whose sufficiency proof itself is a linear time Real RAM algorithm for drawing a funnel on the plane that corresponds to an F-graph. We next give a linear-time algorithm for recognizing an F-graph. When the algorithm recognizes an F-graph, it also reports one of the Hamiltonian cycles defining the boundary of its corresponding funnel. This recognition algorithm takes linear time even on a RAM. We finally show that an F-graph is weakly triangulated and therefore perfect, which agrees with the fact that perfect graphs are related to geometric structures. [ABSTRACT FROM AUTHOR]

An O(¦ E¦log n) algorithm is presented to construct the visibility graph for a collection of n nonintersecting line segments, where ¦ E¦ is the number of edges in the visibility graph. This algorithm is much faster than the O( n )-time and O( n )-space algorithms by Asano et al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses only O( n) working storage. [ABSTRACT FROM AUTHOR]

Let P be a triangulated simple polygon with n sides. The visibility graph of P has an edge between every pair of polygon vertices that can be connected by an open segment in the interior of P. We describe an algorithm that finds the visibility graph of P in O( m) time, where m is the number of edges in the visibility graph. Because m can be as small as O( n), the algorithm improves on the more general visibility algorithms of Asano et al. [AAGHI] and Welzl [W], which take Θ( n ) time, and on Suri's O( m log n) visibility graph algorithm for simple polygons [S]. [ABSTRACT FROM AUTHOR]

Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in O( n ) time and space, a data structure from which in O( n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed in O( n ) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed in O( n ) time, improving earlier O( n log n) results. [ABSTRACT FROM AUTHOR]

A polygon P is said to be a palm polygon if there exists a point x∈ P such that the Euclidean shortest path from x to any point y∈ P makes only left turns or only right turns. The set of all such points x is called the palm kernel. In this paper we propose an O( E) time algorithm for recognizing a palm polygon P, where E is the size of the visibility graph of P. The algorithm recognizes the given polygon P as a palm polygon by computing the palm kernel of P. If the palm kernel is not empty, P is a palm polygon. [ABSTRACT FROM AUTHOR]

A complex network and chaos-based method, based on the visibility graph algorithm, is applied to study particle fluctuations in π--AgBr interactions at 350 GeV with respect to the shower multiplicity dependence. The fractal structure of the fluctuations is studied by using the power of scale freeness of visibility graph (PSVG). The selection of visibility graph as the type of complex network for our analysis is justified as this algorithm gives the most precise result with finite number of data points and this experiment has finite number of events. The topological parameters along with PSVG values are extracted and analysed. The analysis shows that the fractality character is weaker for the lowest multiplicity bin and is stronger for the highest multiplicity bin. [ABSTRACT FROM AUTHOR]