A hierarchical graph 𝒢 consists of a vertex set V(𝒢) and L pairwise disjoint edge sets E_1, … , E_L. Such a structure naturally defines a hierarchy of L unweighted graphs, where the 𝓁-th graph is G_𝓁 = (V, ⋃_{i=1}^𝓁 E_i). In this paper, we initiate the study of hierarchical spanners, namely subgraphs of 𝒢 that approximately preserve distances among a given set of pairs of vertices in V(𝒢) at every level of the hierarchy. This notion generalizes classical spanners, and thus all known lower bounds extend to this setting; however, it is not clear whether the same size-stretch trade-offs can be achieved. We investigate this question by devising both upper and lower bounds for hierarchical spanners under various types of stretch and pairs of vertices of interest whose approximate (or exact) distances are to be maintained. On the positive side, a trivial adaptation of the greedy construction yields (2k-1)-spanners of size O(n^{1+1/k}), matching the classical bounds. However, the non-hierarchical bounds do not extend to the hierarchical case when additive or nearly-additive spanners are considered. For instance, we prove that any β-additive single-pair hierarchical spanner must have size Ω (n √{n/(β+1)}) in the worst case. This bound is tight, as we provide a matching upper bound for every β ≥ 0, which in turn implies a O(n√n)-size single-pair hierarchical preserver. Finally, we present additional positive results among which a 4-additive all-pairs hierarchical spanner of size Õ(n^{5/3}), an (essentially tight) single-source hierarchical (1+ε)-spanner of size Õ(n/ε), an all-pairs hierarchical spanner of size Õ(n√{n/(ε)}) achieving stretch (1+ε,2), for any constant value of ε > 0, and a subsetwise hierarchical preserver of size O(n √{n|S|}), where S ⊆ V(𝒢).

In a temporal forest each edge has an associated set of time labels that specify the time instants in which the edges are available. A temporal path from vertex $u$ to vertex $v$ in the forest is a selection of a label for each edge in the unique path from $u$ to $v$, assuming it exists, such that the labels selected for any two consecutive edges are non-decreasing. We design linear-size data structures that maintain a temporal forest of rooted trees under addition and deletion of both edge labels and singleton vertices, insertion of root-to-node edges, and removal of edges with no labels. Such data structures can answer temporal reachability, earliest arrival, and latest departure queries. All queries and updates are handled in polylogarithmic worst-case time. Our results can be adapted to deal with latencies. More precisely, all the worst-case time bounds are asymptotically unaffected when latencies are uniform. For arbitrary latencies, the update time becomes amortized in the incremental case where only label additions and edge/singleton insertions are allowed as well as in the decremental case in which only label deletions and edge/singleton removals are allowed. To the best of our knowledge, the only previously known data structure supporting temporal reachability queries is due to Brito, Albertini, Casteigts, and Travençolo [Social Network Analysis and Mining, 2021], which can handle general temporal graphs, answers queries in logarithmic time in the worst case, but requires an amortized update time that is quadratic in the number of vertices, up to polylogarithmic factors.

Proton therapy is a cancer therapy that is more expensive than classical radiotherapy but that is considered the gold standard in several situations. Since there is also a limited amount of delivering facilities for this techniques, it is fundamental to increase the number of treated patients over time. The objective of this work is to offer an insight on the problem of the optimization of the part of the delivery time of a treatment plan that relates to the movements of the system. We denote it as the Nozzle Travel Time Problem (NTTP), in analogy with the Leaf Travel Time Problem (LTTP) in classical radiotherapy. In particular this work: (i) describes a mathematical model for the delivery system and formalize the optimization problem for finding the optimal sequence of movements of the system (nozzle and bed) that satisfies the covering of the prescribed irradiation directions; (ii) provides an optimization pipeline that solves the problem for instances with an amount of irradiation directions much greater than those usually employed in the clinical practice; (iii) reports preliminary results about the effects of employing two different resolution strategies within the aforementioned pipeline, that rely on an exact Traveling Salesman Problem (TSP) solver, Concorde, and an efficient Vehicle Routing Problem (VRP) heuristic, VROOM.

Let $G$ be a directed graph with $n$ vertices and $m$ edges, and let $s \in V(G)$ be a designated source vertex. We consider the problem of single source reachability (SSR) from $s$ in presence of failures of edges (or vertices). Formally, a spanning subgraph $H$ of $G$ is a {\em $k$-Fault Tolerant Reachability Subgraph ($k$-FTRS)} if it has the following property. For any set $F$ of at most $k$ edges (or vertices) in $G$, and for any vertex $v\in V(G)$, the vertex $v$ is reachable from $s$ in $G-F$ if and only if it is reachable from $s$ in $H - F$. Baswana et.al. [STOC 2016, SICOMP 2018] showed that in the setting above, for any positive integer $k$, we can compute a $k$-FTRS with $2^k n$ edges. In this paper, we give a much simpler algorithm for computing a $k$-FTRS, and observe that it extends to higher connectivity as well. Our results follow from a simple application of \emph{important separators}, a well known technique in Parameterized Complexity.

Let G be an n-node and m-edge positively real-weighted undirected graph. For any given integer $$f \ge 1$$ , we study the problem of designing a sparse f-edge-fault-tolerant (f-EFT) $$\sigma $$ -approximate single-source shortest-path tree ( $$\sigma $$ -ASPT), namely a subgraph of G having as few edges as possible and which, following the failure of a set F of at most f edges in G, contains paths from a fixed source that are stretched by a factor of at most $$\sigma $$ . To this respect, we provide an algorithm that efficiently computes an f-EFT $$(2|F|+1)$$ -ASPT of size O(fn). Our structure improves on a previous related construction designed for unweighted graphs, having the same size but guaranteeing a larger stretch factor of $$3(f+1)$$ , plus an additive term of $$(f+1) \log n$$ . Then, we show how to convert our structure into an efficient f-EFT single-source distance oracle, that can be built in $$O(f m\, \alpha (m,n)+fn \log ^3 n)$$ time, has size $$O(fn \log ^2 n)$$ , and in $$O(|F|^2 \log ^2 n)$$ time is able to report a $$(2|F|+1)$$ -approximate distance from the source to any node in $$G-F$$ . Moreover, our oracle can return a corresponding approximate path in the same amount of time plus the path’s size. The oracle is obtained by tackling another fundamental problem, namely that of updating a minimum spanning forest (MSF) of G following a batch of k simultaneous modification (i.e., edge insertions, deletions and weight changes). For this problem, we build in $$O(m \log ^3 n)$$ time an oracle of size $$O(m \log ^2 n)$$ , that reports in $$O(k^2 \log ^2 n)$$ time the (at most 2k) edges either exiting from or entering into the MSF. Finally, for any integer $$k \ge 1$$ , we complement all our results with a lower bound of $$\Omega \left( n^{1+\frac{1}{k}}\right) $$ to the size of any f-EFT $$\sigma $$ -ASPT with $$f \ge \log n$$ and $$\sigma < \frac{3k+1}{k+1}$$ , that holds if the Erdős’ girth conjecture is true.

This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of n bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gąsieniec et al., SOFSEM'17] as the Bamboo Garden Trimming (BGT) problem , where the goal is that of computing a perpetual schedule (i.e., the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the makespan , i.e., the maximum height ever reached by a bamboo. Two natural strategies are Reduce-Max and Reduce-Fastest ( x ). Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest ( x ) trims the fastest growing bamboo among the ones that are taller than x . It is known that Reduce-Max and Reduce-Fastest ( x ) achieve a makespan of O ( log ⁡ n ) and 4 for the best choice of x = 2 , respectively. We prove the first constant upper bound of 9 for Reduce-Max and improve the one for Reduce-Fastest ( x ) to 3 + 5 2 < 2.62 for x = 1 + 1 5 . Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to quickly determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a Trimming Oracle data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by Reduce-Max and Reduce-Fastest ( x ).

A tree $$\sigma $$ -spanner of a positively real-weighted n-vertex and m-edge undirected graph G is a spanning tree T of G which approximately preserves (i.e., up to a multiplicative stretch factor $$\sigma $$ ) distances in G. Tree spanners with provably good stretch factors find applications in communication networks, distributed systems, and network design. However, finding an optimal or even a good tree spanner is a very hard computational task. Thus, if one has to face a transient edge failure in T, the overall effort that has to be afforded to rebuild a new tree spanner (i.e., computational costs, set-up of new links, updating of the routing tables, etc.) can be rather prohibitive. To circumvent this drawback, an effective alternative is that of associating with each tree edge a best possible (in terms of resulting stretch) swap edge—a well-established approach in the literature for several other tree topologies. Correspondingly, the problem of computing all the best swap edges of a tree spanner is a challenging algorithmic problem, since solving it efficiently means to exploit the structure of shortest paths not only in G, but also in all the scenarios in which an edge of T has failed. For this problem we provide a very efficient solution, running in $$O(n^2 \log ^4 n)$$ time, which drastically improves (almost by a quadratic factor in n in dense graphs) on the previous known best result.

In real world applications, important resources like energy are saved by deliberately using so-called low-cost operations that are less reliable. Some of these approaches are based on a dual mode technology where it is possible to choose between high-energy operations (always correct) and low-energy operations (prone to errors), and thus enable to trade energy for correctness. In this work we initiate the study of algorithms for solving optimization problems that in their computation are allowed to choose between two types of operations: high-energy comparisons (always correct but expensive) and low-energy comparisons (cheaper but prone to errors). For the errors in low-energy comparisons, we assume the persistent setting, which usually makes it impossible to achieve optimal solutions without high-energy comparisons. We propose to study a natural complexity measure which accounts for the number of operations of either type separately. We provide a new family of algorithms which, for a fairly large class of maximization problems, return a constant approximation using only polylogarithmic many high-energy comparisons and only O(n log n) low-energy comparisons. This result applies to the class of p-extendible system s [Mestre, 2006], which includes several NP-hard problems and matroids as a special case (p=1). These algorithmic solutions relate to some fundamental aspects studied earlier in different contexts: (i) the approximation guarantee when only ordinal information is available to the algorithm; (ii) the fact that even such ordinal information may be erroneous because of low-energy comparisons and (iii) the ability to approximately sort a sequence of elements when comparisons are subject to persistent errors. Finally, our main result is quite general and can be parametrized and adapted to other error models.

Real life graphs and networks are prone to failure of nodes (vertices) and links (edges). In particular, for a pair of nodes s and t and a failing edge e in an n-vertex unweighted graph G=(V(G),E(G)), the replacement path pi_{G-e}(s,t) is a shortest s-t path that avoids e. In this paper we present several efficient constructions that, for every (s,t) \in S x T, where S, T \subseteq V(G), and every e \in E(G), maintain the collection of all pi_{G-e}(s,t), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles (DSO)), or explicitly (i.e., through sparse subgraphs a.k.a. fault-tolerant preservers (FTP)). More precisely, we provide the following results: (1) DSO: For every S,T \subseteq V(G), we construct a DSO for maintaining S x T distances under single edge (or vertex) faults. This DSO has size tilde{O}(n\sqrt{|S||T|}) and query time of O(\sqrt{|S||T|}). At the expense of having quasi-polynomial query time, the size of the oracle can be improved to tilde{O}(n|S|+|T|\sqrt{|S|n}), which is optimal for |T| = Omega(sqrt{n|S|}). When |T| = Omega(n^frac{3}{4} |S|^frac{1}{4}), the construction can be further refined in order to get a polynomial query time. We also consider the approximate additive setting, and show a family of DSOs that exhibits a tradeoff between the additive stretch and the size of the oracle. Finally, for the meaningful single-source case, the above result is complemented by a lower bound conditioned on the Set-Intersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings. (2) FTP: We show the construction of a path-reporting DSO of size tilde{O}(n^{4/3}(|S||T|)^{1/3}) reporting pi_{G-e}(s,t) in O(|pi_{G-e}(s,t)|+(n|S||T|)^{1/3}) time. Such a DSO can be transformed into a FTP having the same size, and moreover it can be elaborated in order to make it optimal (up to a poly-logarithmic factor) both in space and query time for the special case in which T=V(G). Our FTP improves over previous constructions when |T|=O(sqrt{|S|n}) (up to inverse poly-logarithmic factors). (3) Routing and Labeling Schemes: For the well-studied single-source setting, we present a novel routing scheme, that allows to route messages on pi_{G-e}(s,t) by using edge labels and routing tables of size tilde{O}(\sqrt{n}), and a header message of poly-logarithmic size. We also present a labeling scheme for the setting which is optimal in space up to constant factors.

The rational fair consensus problem can be informally defined as follows. Consider a network of n (selfish) rational agents, each of them initially supporting a color chosen from a finite set Σ. The goal is to design a protocol that leads the network to a stable monochromatic configuration (i.e. a consensus) such that the probability that the winning color is c is equal to the fraction of the agents that initially support c, for any c ∈ Σ. Furthermore, this fairness property must be guaranteed (with high probability) even in presence of any fixed coalition of rational agents that may deviate from the protocol in order to increase the winning probability of their supported colors. A protocol having this property, in presence of coalitions of size at most t, is said to be a whp - t-strong equilibrium. We investigate, for the first time, the rational fair consensus problem in the GOSSIP communication model where, at every round, every agent can actively contact at most one neighbor via a push/pull operation. We provide a randomized GOSSIP protocol that, starting from any initial color configuration of the complete graph, achieves rational fair consensus within O(log n) rounds using messages of O(log2n) size, w.h.p. More in details, we prove that our protocol is a whp t-strong equilibrium for any t = o(n/ log n) and, moreover, it tolerates worst-case permanent faults provided that the number of non-faulty agents is Ω(n). As far as we know, our protocol is the first solution which avoids any all-to-all communication, thus resulting in o(n2) message complexity.

A tree ρ-spanner of a positively real-weighted n-vertex and m-edge undirected graph G is a spanning tree T of G which approximately preserves (i.e., up to a multiplicative stretch factor ρ) distances in G. Tree spanners with provably good stretch factors find applications in communication networks, distributed systems, and network design. However, finding an optimal or even a good tree spanner is a very hard computational task. Thus, if one has to face a transient edge failure in T, the overall effort that has to be afforded to rebuild a new tree spanner (i.e., computational costs, set-up of new links, updating of the routing tables, etc.) can be rather prohibitive. To circumvent this drawback, an effective alternative is that of associating with each tree edge a best possible (in terms of resulting stretch) swap edge -A well-established approach in the literature for several other tree topologies. Correspondingly, the problem of computing all the best swap edges of a tree spanner is a challenging algorithmic problem, since solving it efficiently means to exploit the structure of shortest paths not only in G, but also in all the scenarios in which an edge of T has failed. For this problem we provide a very efficient solution, running in O(n2log4n) time, which drastically improves (almost by a quadratic factor in n in dense graphs!) on the previous known best result.

Let s denote a distinguished source vertex of a non-negatively real weighted and undirected graph G with n vertices and m edges. In this paper we present two efficient single-source approximate-distance sensitivity oracles, namely compact data structures which are able to quickly report an approximate (by a multiplicative stretch factor) distance from s to any node of G following the failure of any edge in G. More precisely, we first present a sensitivity oracle of size O(n) which is able to report 2-approximate distances from the source in O(1) time. Then, we further develop our construction by building, for any 0<epsilon<1, another sensitivity oracle having size O(n*1/epsilon*log(1/epsilon)), and is able to report a (1+epsilon)-approximate distance from s to any vertex of G in O(log(n)*1/epsilon*log(1/epsilon)) time. Thus, this latter oracle is essentially optimal as far as size and stretch are concerned, and it only asks for a logarithmic query time. Finally, our results are complemented with a space lower bound for the related class of single-source additively-stretched sensitivity oracles, which is helpful to realize the hardness of designing compact oracles of this type.

The resiliency of a network is its ability to remain effectively functioning also when any of its nodes or links fails. However, to reduce operational and set-up costs, a network should be small in size, and this conflicts with the requirement of being resilient. In this paper we address this trade-off for the prominent case of the broadcasting routing scheme, and we build efficient (i.e., sparse and fast) fault-tolerant approximate shortest-path trees, for both the edge and vertex single-failure case. In particular, for an n-vertex non-negatively weighted graph, and for any constant ε > 0, we design two structures of size O(nlogn/ε^2) which guarantee (1 + ε)-stretched paths from the selected source also in the presence of an edge/vertex failure. This favorably compares with the currently best known solutions, which are for the edge-failure case of size O(n) and stretch factor 3, and for the vertex-failure case of size O(n logn) and stretch factor 3. Moreover, we also focus on the unweighted case, and we prove that an ordinary (α,β)-spanner can be slightly augmented in order to build efficient fault-tolerant approximate breadth-first-search trees.

Network creation games have been extensively studied, both from economists and computer scientists, due to their versatility in modeling individual-based community formation processes, which in turn are the theoretical counterpart of several economics, social, and computational applications on the Internet. However, the generally adopted assumption is that players have a common and complete information about the ongoing network, which is quite unrealistic in practice. In this paper, we consider a more compelling scenario in which players have only limited information about the network they are embedded in. More precisely, we explore the game theoretic and computational implications of assuming that players have a view of the network restricted to their k-neighborhood, which is one of the most qualified ,local-knowledge models used in distributed computing. To this respect, we define a suitable equilibrium concept and we provide a comprehensive set of upper and lower bounds to the price of anarchy for the entire range of values of k.

Let G=(V,E) be a graph modeling a network where each edge is owned by a selfish agent, which establishes the cost for using her edge by pursuing only her personal utility. In such a setting, several classic network optimization problems, like for instance many graph traversal problems, asks for solutions in which an edge of G can be used several times. In game-theoretic terms, these problems are known as one-parameter problems, but with a peculiarity: the workload of each agent is a natural number. In this paper we refine the classic notion of monotonicity of an algorithm so as to exactly capture this property, and we then provide a general technique to efficiently develop truthful mechanisms for this family of problems.

Abstract Let a communication network be modeled by an undirected graph $G=(V,E)$ of n nodes and m edges, and assume that edges are controlled by selfish agents, which privately hold the length of each owned edge. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most popular network topologies, i.e. the single‐source shortest paths tree. More precisely, we study several realistic scenarios, in which each agent can own either a single edge or multiple edges of G. In particular, for the single‐edge scenario, we show that in the utilitarian case the problem can be efficiently solved in $O(mn \log{}\alpha(m,n))$ time, while in a meaningful non‐utilitarian case, namely that in which agents' valuation functions depend only on the edge lengths, it can be solved in $O(m + n \log n)$ time. On the other hand, for the multiple‐edge scenario, in the utilitarian case we show an $O(mn+n^2 \log n)$ time truthful mechanism, while in the same non‐utilitarian case we provide an n‐approximate truthful mechanism which can be implemented in $O(m n \,\alpha(m,n))$ time. We also show that in the special case in which, for every agent, the owned edges are all incident to the same node, then this latter mechanism has an almost optimal $O(m\,\alpha(m,n))$ runtime. Copyright © 2007 John Wiley & Sons, Ltd.

Let a communication network be modelled by a graph G=(V,E) of n nodes and m edges. Classic communication operations among nodes in the graph (e.g., broadcasting, multicasting, gossiping, etc.) usually take place on a subgraph of G, which is built in such a way that a given objective function is optimized. Among the many possible topologies of such a subgraph, the minimum radius spanning tree (MRST) is a rooted tree which minimizes the distance from the root to a farthest node. The MRST finds a natural application in several facility location problems, since it allows to minimize the maximum delay for reaching the center from the periphery of the tree. In this paper, we consider the problem of computing an MRST in a non-cooperative setting in which each edge of G is controlled by a selfish agent, and the cost she asks for using her edge depends only on her private information. Under these assumptions, we provide a mechanism that computes a true MRST of G in O(mn√n+n3 log n) time and O(n2 √n) space. Interestingly, this is just at most a linear factor away from the time needed to compute an MRST in a canonical centralized framework.

Spatial data appear in numerous applications, such as GIS, multimedia and even traditional databases. Most of the analysis on spatial data has focused on point data, typically using the uniformity assumption, or, more accurately, a fractal distribution. However, no results exist for nonpoint spatial data, like 2D regions (e.g., islands), 3D volumes (e.g., physical objects in the real world), etc. This is exactly the problem we solve in this paper. Based on experimental evidence that real areas and volumes follow a "power law," that we named REGAL (REGion Area Law), we show 1) the theoretical implications of our model and its connection with the ubiquitous fractals and 2) the first of its practical uses, namely, the selectivity estimation for range queries. Experiments on a variety of real data sets (islands, lakes, and human-inhabited areas) show that our method is extremely accurate, enjoying a maximum relative error ranging from 1 to 5 percent, versus 30-70 percent of a naive model that uses the uniformity assumption.

In this paper, we study the node distribution of an R-tree storing region data, like, for instance, islands, lakes, or human-inhabited areas. We will show that real region datasets are packed in an R-tree into minimum bounding rectangles (MBRs) whose area distribution follows the same power law, named REGAL (REGion Area Law), as that for the regions themselves. Moreover, these MBRs are packed in their turn into MBRs following the same law, and so on iteratively, up to the root of the R-tree. Based on this observation, we are able to accurately estimate the search effort for range queries, using a small number of easy-to-retrieve parameters. Furthermore, since our analysis exploits, through a realistic mathematical model, the proximity relations existing among the regions in the dataset, we show how to use our model to predict the selectivity of a self-spatial join query posed on the dataset. Experiments on a variety of real datasets (islands, lakes, human-inhabited areas) show that our estimations are accurate, enjoying a geometric average relative error ranging from 22 percent to 32 percent for the search effort of a range query, and from 14 percent to 34 percent for the selectivity of a self-spatial join query. This is significantly better than using a naive model based on uniformity assumption, which gives rise to a geometric average relative error up to 270 percent and up to 85 percent for the two problems, respectively.

We study the node distribution of an R-tree storing region data, like for instance islands, lakes or human-inhabited areas. We show that real region datasets are packed in minimum bounding rectangles (MBRs) whose area distribution follows the same power law, named REGAL (REGion Area Law), as that for the regions themselves. Moreover these MBRs are packed in their turn into MBRs following the same law, and so on iteratively, up to the root of the R-tree. Based on this observation, we are able to accurately estimate the search effort for range queries, the most prominent spatial operation, using a small number of easy-to-retrieve parameters. Experiments on a variety of real datasets (islands, lakes, human-inhabited areas) show that our estimation is accurate, enjoying a maximum geometric average relative error within 30%.

Existing featureless image mosaicing techniques do not pay enough attention to the robustness of the image registration process, and are not able to combine multiple video sequences into an integrated panoramic view. These problems have certainly restricted applications of the existing methods for large-scale panorama composition, video content overview and information visualization. In this paper we propose a method that is able to create an integrated panoramic view for a virtual camera from multiple video sequences which each records a part of a vast scene. The method further enables the user to visualize the integrated panoramic view from an arbitrary viewpoint and orientation by altering the parameters of the virtual camera. To ensure a robust and accurate panoramic view synthesis from long video sequences, we attach a global positioning system (GPS) to the video camera, and utilize its output data to provide initial estimates for the camera's translational parameters, and to prevent the camera parameter recovery process from falling into spurious local minima. Our proposed method is not only suitable for video content overview but also applicable to the areas of information visualization, team collaborations, disastrous rescues, etc. The experimental results demonstrate the effectiveness of the proposed method.

Despite of the fact that large line segment datasets are becoming more and more popular, most of the analysis for estimating the selectivity of window queries posed on spatial data --the most important parameter for query optimization-- has focused on point or region data only. In this paper we move one significant step forward in line segment datasets theoretical analysis. We discovered that real lines closely follow a distribution law, that we named the SLED law (Segment LEngth Distribution). The SLED law can be used for an accurate estimation of the selectivity of window queries. Experiments on a variety of real line segment datasets (hydrographic systems, roadmaps, railroads, utilities networks) show that our law holds and that our formula is extremely accurate, enjoying a maximum relative error of 4% in estimating the selectivity. 1 On leave from Dipartimento di Matematica Pura ed Applicata, University of L'Aquila, Via Vetoio, I-67010, Italy. His research was partially supported ...

We propose a new image retrieval method based on human perceptual clustering of color images. This color clustering produces for each image a small set of representative colors which captures the color properties of the image, and a small set of sizable contiguous regions which captures the spatial/geometrical properties of the image. The proposed method outperforms the traditional histogram and its improved methods not only with its richer image retrieval capabilities which cover a wider spectrum of user requirements, but also with its powerful indexing scheme which is essential to cater for large scale image databases.

Traditionalrandom models for spatial two-dimensional data proposed in literature show their limits in generating in a satisfactory way instances of regions having a desired aggregation level.This is because none of them is really oriented to this aim.Rather, they are thought to model the behaviour of the constituting elements of the spatial data (so loosing sight of the context), or, alternatively, to model particular data structure for their representation, underestimating the fact that there is in general no semantic link between a region data and its representation.This means from one hand, the impossibility to produce meaningful the oretical results on time and space average performances of different data structures used to represent spatial regions, and, on the other hand, in an applicative context, the difficulty to generate instances of spatial regions having a statistical behaviour close to that of real data.To overcome this trouble, we introduce in our paper a new random model that provides the possibility to generate spatial regions having a desired aggregation.

In this paper we propose and analyze a new meaningful branching sequence to generate random quadtrees representing binary images. In particular, we show that this sequence produces expected distributions of external and internal nodes much closer to real data than all previous proposed approaches in the literature to model both random binary images and quadtrees. This new model provides a good compromise in representing images belonging to various classes, more or less structured. The effectiveness of the new proposed model is shown through a comparison with respect to nodes distributions of representative real spatial data images. The introduction of this new realistic model can have a large impact on the analysis of expected performances of a large class of algorithms for spatial data processing. First experimental results show that this new model closely simulate real cases.>

The conceptual framework and the design of the prototype of a common toolkit for map and office document interpretation developed in the ROCKI project are described. The conceptual framework features a novel three-step knowledge-based approach to the interpretation process. The first is the primitive interpretation which identifies elementary graphical objects. These are further processed (object interpretation) to obtain basic structured objects, which are finally (document interpretation) grouped into objects with associated semantics, obtaining a full description of the document. The design takes into account the need for feedback and cooperation among the different steps.>