In case of a future pandemic, the mobility dynamics of a city can be controlled by intervening in the mobility patterns of people. Instead of hard quarantine policies, incentives can be designed that are compatible with people's preferences. At first, we distinguish mobility from the different types of locations for which distance matters. We match these types of locations in a way that maximizes the natural preference of people to visit the locations. We investigate different approaches for matching locations, such as retail and educational services, while considering people's preferences. We show that satisfying the preferences of the entire city is a computationally hard problem. Approximation algorithms are proposed in which the penalty for preference violation is bounded. We propose a fast approximation algorithm that focuses on the penalty value of locations, and we propose a more computationally heavy approximation that focuses on user penalty with a specific scheme of user allocation to locations. Additionally, we investigated higher-order matching of locations and the complexity of urban partitioning. We tested our approach in Euclidean space and network space. Finally, we show that applying such mobility restrictions can reduce the transmission rate, and we extract cells whose people can be incentivized to fulfill their needs based on the proposed algorithms, slowing down a future pandemic and preventing potential superspreading events.

Abstract Bipartite graphs are commonly used to visualize objects and their features. An object may possess several features and several objects may share a common feature. The standard visualization of bipartite graphs, with objects and features on two (say horizontal) parallel lines at integer coordinates and edges drawn as line segments, can often be difficult to work with. A common task in visualization of such graphs is to consider one object and all its features. This naturally defines a drawing window, defined as the smallest interval that contains the x-coordinates of the object and all its features. We show that if both objects and features can be reordered, minimizing the average window size is NP-hard. However, if the features are fixed, then we provide an efficient polynomial-time algorithm for arranging the objects, so as to minimize the average window size. Finally, we introduce a different way of visualizing the bipartite graph, by placing the nodes of the two parts on two concentric circles. For this setting we also show NP-hardness for the general case and a polynomial-time algorithm when the features are fixed.

Driver distraction caused by over-reliance on automotive technology is one of the leading causes of accidents in semi-autonomous vehicles. Existing driver's attention-gauging approaches are intrusive and as such emphasize constant driver engagement. In case of an urgent traffic event, they fail to measure the event's criticality and subsequently generate timely alerts. In this paper, we re-position the driver's attention-gauging approach as a way to improve the driver's situational awareness during critical situations. We exploit how a vehicle captures its surroundings information to convert an automotive decision into defining the criticality and timeliness of an alert. For this, we identify the relationship between the traffic event, the type of automotive sensing technologies, and its processing resources to capture that event to design the driver's attention gauge. We evaluate the timeliness of alerts for different traffic scenarios over a prototype built using NVIDIA Jetson Xavier AGX and Carla. Our results show that we can improve the timeliness of an alert by up to 75x as compared to existing state-of-the-art approaches, while also providing feedback on its criticality.

Due to increasing concerns of data privacy, databases are being encrypted before they are stored on an untrusted server. To enable search operations on the encrypted data, searchable encryption techniques have been proposed. Representative schemes use order-preserving encryption (OPE) for supporting efficient Boolean queries on encrypted databases. Yet, recent works showed the possibility of inferring plaintext data from OPE-encrypted databases, merely using the order-preserving constraints, or combined with an auxiliary plaintext dataset with similar frequency distribution. So far, the effectiveness of such attacks is limited to single-dimensional dense data (most values from the domain are encrypted), but it remains challenging to achieve it on high-dimensional datasets (e.g., spatial data), which are often sparse in nature. In this paper, for the first time, we study data inference attacks on multi-dimensional encrypted databases (with 2-D as a special case). We formulate it as a 2-D order-preserving matching problem and explore both unweighted and weighted cases, where the former maximizes the number of points matched using only order information and the latter further considers points with similar frequencies. We prove that the problem is NP-hard, and then propose a greedy algorithm, along with a polynomial-time algorithm with approximation guarantees. Experimental results on synthetic and real-world datasets show that the data recovery rate is significantly enhanced compared with the previous 1-D matching algorithm.

We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric problems: we construct the greedy multi-fragment tour for Euclidean TSP in $O(n\log n)$ time in any fixed dimension and for Steiner TSP in planar graphs in $O(n\sqrt{n}\log n)$ time; we compute motorcycle graphs (which are a central part in straight skeleton algorithms) in $O(n^{4/3+\varepsilon})$ time for any $\varepsilon>0$; we introduce a narcissistic variant of the $k$-attribute stable matching model, and solve it in $O(n^{2-4/(k(1+\varepsilon)+2)})$ time; we give a linear-time $2$-approximation for a 1D geometric set cover problem with applications to radio station placement.

With the ubiquitous adoption of smartphones and mobile devices, it is now common practice for one's location to be sensed, collected and likely shared through social platforms. While such data can be helpful for many applications, users start to be aware of the privacy issue in handling location and trajectory data. While some users may voluntarily share their location information (e.g., for receiving location-based services, or for crowdsourcing systems), their location information may lead to information leaks about the whereabouts of other users, through the co-location of events when two users are at the same location at the same time and other side information, such as upper bounds of movement speed. It is therefore crucial to understand how much information one can derive about other's positions through the co-location of events and occasional GPS location leaks of some of the users. In this paper we formulate the problem of inferring locations of mobile agents, present theoretically-proven bounds on the amount of information that could be leaked in this manner, study their geometric nature, and present algorithms matching these bounds. We will show that even if a very weak set of assumptions is made on trajectories' patterns, and users are not obliged to follow any 'reasonable' patterns, one could infer very accurate estimation of users' locations even if they opt not to share them. Furthermore, this information could be obtained using almost linear-time algorithms, suggesting the practicality of the method even for huge volumes of data.

In the relay placement problem, the input is a set of sensors and a number r ⩾ 1, the communication range of a relay. In the one-tier version of the problem, the objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance 1 otherwise. The two-tier version adds the restrictions that the path must go through relays, and not through sensors . We present a 3.11-approximation algorithm for the one-tier version and a polynomial-time approximation scheme (PTAS) for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P ≠ NP.

We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.

Providing healthcare to the remote and isolated communities in the Brazilian Amazon poses a significant challenge. In those places, healthcare examinations are mainly run by sporadic visits from medical teams from the main city in the region, Belém. An alternative would be to have local nurses or technicians perform routine clinical examinations, such as ultrasounds on pregnant women, elec whose records could be sent to the doctors in Belém for evaluation. However, due to the lack of modern communication infrastructure in these communities, we propose the use of regularly scheduled boats as data mules to ensure fast and timely delivery of the examination records from those communities to physicians in the city for remote analysis. Unpredictable boat delays and break-downs, as well as high transmission failures due to the harsh environment in the region, mandate the design of robust delay-tolerant routing algorithms. The main contributions of this paper are two-fold: First, we propose the use of fountain codes in order to improve the robustness of opportunistic data routing. Second, we develop a simulation model that incorporates the high unpredictability of the Amazon riverine scenario, accounting for boat delays/breakdowns environmental conditions and individual packet losses, and present extensive simulations results to evaluate our proposed approaches. While the results in this paper focus on remote healthcare applications in the Brazilian Amazon, we envision that our approach may also be used for other remote applications, such as distance education, and other similar scenarios.

Wireless communication systems, such as RFIDs and wireless sensor networks, are increasingly being used in security-sensitive applications, e.g. credit card transactions or monitoring patient health in hospitals. Wireless jamming by transmitting artificial noise, which is traditionally used as an offensive technique for disrupting communication, has recently been explored as a means of protecting sensitive communication from eavesdroppers.

Security-sensitive applications, such as patient health monitoring and credit card transactions, are increasingly utilizing wireless communication systems, RFIDs, wireless sensor networks, and other wireless communication systems. The use of interference-emitting jammers to protect these sensitive communications has been recently explored in the literature, and has shown high potential. In this paper we consider optimization problems relating to the temporal distributions of jammers' activity, and the suitable coding regimes used for communication. Solving the joint problem optimally enables comprehensive security in space, at a low power consumption and low communication overhead. The joint optimization of jamming in space and time is driven by a new framework that uses the bit-error probability as a measure of communication quality. Under this framework, we show how to guarantee information-theoretic security within a geographic region, and with increased flexibility to tailor the coding regime to the problem's geometry. We present efficient algorithms for different settings, and provide simulations for various scenarios using the bit-error probability functions. These simulations demonstrate the efficiency of the scheme. We believe that our scheme can lead to practical, economical and scalable solutions for providing another layer of protection of sensitive data, in cases where encryption schemes are limited or impractical.

Mountainous regions are typically hard to access by land; because of this, search operations in hilly terrains are often performed by airborne force such as Unmanned Aerial Vehicles (UAVs). We give algorithms for motion planning and coordination for a team of UAVs under various assumptions on the vehicles equipage/capabilities and present outputs of an implementation of the algorithms.

Telecommunications networks, and in particular optical WDM networks, are vulnerable to large-scale failures in their physical infrastructure, resulting from physical attacks (such as an electromagnetic pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network, but their effects cannot be determined exactly in advance. Therefore, we provide a unified framework to model network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, when network components consist of several dependent subcomponents, and in which either a 1+1 or a 1:1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, demonstrating the applicability of our algorithms to real-world scenarios. Our novel approach allows to identify locations that require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience.

We propose algorithms for computing optimal trajectories of a group of flying observers (such as helicopters or UAVs) searching for a lost child in a hilly terrain. Very few assumptions are made about the speed or direction of the child's motion and whether it might (either deliberately or accidentally) try to avoid being found. This framework can also be applied to seekers searching for hostile evaders, such as smugglers/criminals, or friendly evaders, such as lost hikers.

Failures in fiber-optic networks may be caused by natural disasters, such as floods or earthquakes, as well as other events, such as an Electromagnetic Pulse (EMP) attack. These events occur in specific geographical locations, therefore the geography of the network determines the effect of failure events on the network's connectivity and capacity. In this paper we consider a generalization of the min-cut and max-flow problems under a geographic failure model. Specifically, we consider the problem of finding the minimum number of failures, modeled as circular disks, to disconnect a pair of nodes and the maximum number of failure disjoint paths between pairs of nodes. This model applies to the scenario where an adversary is attacking the network multiple times with intention to reduce its connectivity. We present a polynomial time algorithm to solve the geographic min-cut problem and develop an ILP formulation, an exact algorithm, and a heuristic algorithm for the geographic max-flow problem.

Flash memory devices commonly rely on traditional address mapping schemes such as page mapping, block mapping or a hybrid of the two. Page mapping is more flexible than block mapping or hybrid mapping without being restricted by block boundaries. However, its mapping table tends to grow large quickly as the capacity of flash memory devices does. To overcome this limitation, we propose a novel mapping scheme that is fundamentally different from the existing mapping strategies. We call this new scheme Virtual Extent Trie (VET), as it manages mapping information by treating each I/O request as an extent and by using extents as basic mapping units rather than pages or blocks. By storing extents instead of individual addresses, VET consumes much less memory to store mapping information and still remains as flexible as page mapping. We observed in our experiments that VET reduced memory consumption by up to an order of magnitude in comparison with the traditional mapping schemes for several real world workloads. The VET scheme also scaled well with increasing address spaces by synthetic workloads. With a binary search mechanism, VET limits the mapping time to O(log log|U |), where U denotes the set of all possible logical addresses. Though the asymptotic mapping cost of VET is higher than the O(1) time of a page mapping scheme, the amount of increased overhead was almost negligible or low enough to be hidden by an accompanying I/O operation.

A significant part of many videos of lectures is presentation slides that occupy much of the field of view. Further, for a student studying the lecture, having the slides sharply displayed is especially important, compared with the speaker, background, and audience. However, even if the original capture supports it, the bandwidth required for real time viewing is substantive, especially in the context of mobile devices. Here we propose reconstructing the video on the client side by backprojecting high resolution slide images into the video stream with the slide area blacked out. The high resolution slide deck can be sent once, and inserted into the video on the client side based on the transformation (a homography) computed in advance. We further introduce the idea that needed homography transformations can be approximated using affine transformations, which allows it to be done using built-in capabilities of HTML 5. We find that it is possible to significantly reduce bandwidth by compressing the modified video, while improving the slide area quality, but leaving the non-slide area roughly the same.

In this paper, we study strategies for allocating and managing friendly jammers, so as to create virtual barriers that would prevent hostile eavesdroppers from tapping sensitive wireless communication. Our scheme precludes the use of any encryption technique. Applications include domains such as (i) protecting the privacy of storage locations where RFID tags are used for item identification, (ii) secure reading of RFID tags embedded in credit cards, (iii) protecting data transmitted through wireless networks, sensor networks, etc. By carefully managing jammers to produce noise, we show how to reduce the SINR of eavesdroppers to below a threshold for successful reception, without jeopardizing network performance.

Nearest-neighbor queries, which ask for returning the nearest neighbor of a query point in a set of points, are important and widely studied in many fields because of a wide range of applications. In many of these applications, such as sensor databases, location based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest neighbor queries in a probabilistic framework in which the location of each input point and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance, which we refer to as the expected nearest neighbor (ENN). We present methods for computing an exact ENN or an ε-approximate ENN, for a given error parameter 0 < ε 0 < 1, under different distance functions. These methods build an index of near-linear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or ε-approximate ENN queries with provable performance guarantees.

Telecommunications networks, and in particular optical WDM networks, are vulnerable to large-scale failures of their physical infrastructure, resulting from physical attacks (such as an Electromagnetic Pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network but their effects are not deterministic. Therefore, we provide a unified framework to model the network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, in which network components consist of several dependent subcomponents, and in which either a 1+1 or a 1:1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, thereby demonstrating the applicability of our algorithms to real-world scenarios. Our novel approach allows for identifying locations which require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience.

We present a system that assists users in viewing videos of lectures on small screen devices, such as cell phones. It automatically identifies semantic units on the slides, such as bullets, groups of bullets, and images. As the participant views the lecture, the system magnifies the appropriate semantic unit while it is the focus of the discussion. The system makes this decision based on cues from laser pointer gestures and spoken words that are read off the slide. It then magnifies the semantic element using the slide image and the homography between the slide image and the video frame. Experiments suggest that the semantic units of laser-based events identified by our algorithm closely match those identified by humans. In the case of identifying bullets through spoken words, results are more limited but are a good starting point for more complex methods. Finally, we show that this kind of magnification has potential for improving learning of technical content from video lectures when the resolution of the video is limited, such as when being viewed on hand held devices.

We describe a robust and efficient method for automatically matching and time-aligning electronic slides to videos of corresponding presentations. Matching electronic slides to videos provides new methods for indexing, searching, and browsing videos in distance-learning applications. However, robust automatic matching is challenging due to varied frame composition, slide distortion, camera movement, low-quality video capture, and arbitrary slides sequence. Our fully automatic approach combines image-based matching of slide to video frames with a temporal model for slide changes and camera events. To address these challenges, we begin by extracting scale-invariant feature-transformation (SIFT) keypoints from both slides and video frames, and matching them subject to a consistent projective transformation (homography) by using random sample consensus (RANSAC). We use the initial set of matches to construct a background model and a binary classifier for separating video frames showing slides from those without. We then introduce a new matching scheme for exploiting less distinctive SIFT keypoints that enables us to tackle more difficult images. Finally, we improve upon the matching based on visual information by using estimated matching probabilities as part of a hidden Markov model (HMM) that integrates temporal information and detected camera operations. Detailed quantitative experiments characterize each part of our approach and demonstrate an average accuracy of over 95% in 13 presentation videos.

We present a novel method to correct automatically generated speech transcripts of talks and lecture videos using text from accompanying presentation slides. The approach finesses the challenges of dealing with technical terms which are often outside the vocabulary of speech recognizers. Further, we align the transcript to the slide word sequence so that we can improve the organization of closed captioning for hearing impaired users, and improve automatic highlighting or magnification for visually impaired users. For each speech segment associated with a slide, we construct a sequential Hidden Markov Model for the observed phonemes that follows slide word order, interspersed with text not on the slide. Incongruence between slide words and mistaken transcript words is accounted for using phoneme confusion probabilities. Hence, transcript words different from aligned high probability slide words can be corrected. Experiments on six talks show improvement in transcript accuracy and alignment with slide words.

Multi-channel wireless networks are increasingly being employed as infrastructure networks, e.g.\ in metro areas. Nodes in these networks frequently employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth and such a path satisfies the constraint that no two consecutive links on the path are assigned the same channel, referred to as "Channel Discontinuity Constraint" (CDC). CDC-paths are also quite useful for TDMA system, where preferably every consecutive links along a path are assigned different time slots. This paper contains several contributions. We first present an O(N2) distributed algorithm for discovering the shortest CDC-path between given source and destination. For use in wireless networks, we explain how spatial properties can be used for dramatically expedite the algorithm. This improves the running time of the O(N3) centralized algorithm of Ahuja et al. for finding the minimum-weight CDC-path. Our second result is a generalized t-spanner for CDC-path; For any ¿>0 we show how to construct a sub-network containing only O(N/¿) edges, such that that length of shortest CDC-paths between arbitrary sources and destinations increases by only a factor of at most 1/(1-2 sin (¿/2))2. This scheme can be implemented in a distributed manner with a message complexity of O(n log n) and it is highly dynamic, so addition/deletion of nodes are easily handled in a distributed manner. An important conclusion of this scheme is in the case of directional antennas are used. In this case, it is enough to consider only the two closest nodes in each cone.

As the number of applications of sensor networks increases, so does the interest in sensor network localization, that is, in recovering the correct position of each node in a network of sensors from partial connectivity information such as adjacency, range, or angle between neighboring nodes. In this article, we consider the anchor-free localization problem in sensor networks that report possibly noisy range information and angular information about the relative order of each sensor's neighbors. Previously proposed techniques seem to successfully reconstruct the original positions of the nodes for relatively small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with nonconvex or nonsimple underlying topology. Moreover, the distributed nature of the problem makes some of the centralized techniques inapplicable in distributed settings. To address these problems we describe a multiscale dead-reckoning (MSDR) algorithm that scales well for large networks, can reconstruct complex underlying topologies, and is resilient to noise. The MSDR algorithm takes its roots from classic force-directed graph layout computation techniques. These techniques are augmented with a multiscale extension to handle the scalability issue and with a dead-reckoning extension to overcome the problems arising with nonsimple topologies. Furthermore, we show that the distributed version of the MSDR algorithm performs as well as, if not better than, its centralized counterpart, as shown by the quality of the layout, measured in terms of the accuracy of the computed pairwise distances between sensors in the network.

Spatio-temporal alignment of electronic slides with corresponding presentation video opens up a number of possibilities for making the instructional content more accessible and understandable, such as video quality improvement, better content analysis and novel compression approaches for low bandwidth access. However, these applications need finding accurate transformations between slides and video frames, which is quite challenging in capture settings using pan-tilt-zoom (PTZ) cameras. In this paper we present a nonlinear optimization approach for accurate registration of slide images to video frames. Instead of estimating the projective transformation (i.e., homography) between a single pair of slide and frame images, we solve a set of homographies jointly in a frame sequence that is associated with a given slide. Quantitative evaluation confirms that this substantively improves alignment accuracy.

We develop a general framework to automatically match electronic slides to the videos of the corresponding presentations. The synchronized slides support indexing and browsing of educational and corporate digital video libraries. Our approach extends previous work that matches slides based on visual features alone, and integrates multiple cues to further improve performance in more difficult cases. We model slide change in a presentation with a dynamic hidden Markov model (HMM) that captures the temporal notion of slide change and whose transition probabilities are adapted locally by using the camera events in the inference process. Our results show that combining multiple cues in a state model can greatly improve the performance in ambiguous cases.

We consider the centralized, anchor-free sensor localization problem. We consider the case where the sensor network reports range information and the case where in addition to the range, we also have angular information about the relative order of each sensor's neighbors. We experimented with classic and new force-directed techniques. The classic techniques work well for small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with noisy data. We describe a new force-directed technique, based on a multi-scale dead-reckoning, that scales well for large networks, is resilient under range errors, and can reconstruct complex underlying regions.

This work proposes new retransmission and backoff strategies for network-wide broadcasting in multi-hop wireless networks. A comparative analysis is presented between existing algorithms as well as the ones proposed herein. Simulation experiments and analysis are used throughout this work to study or demonstrate the properties and performance of specific strategies as well as other properties or results of a more general nature. Several topics not considered in previous work are also studied. The broadcasting strategies are evaluated with respect to their impact on routing protocols that rely on flooding to perform path discovery, and research is conducted in designing schemes that maximize the route lifetime. Different backoff strategies are proposed and their performance is examined.

We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay [4] as a successful heuristics for pattern matching under translation, where the input consists of two point sets in d-space, for d≥1, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-directional) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, for which we present a lower bound construction of Ω(n logn) iterations under the RMS measure, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case.We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector Δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the relative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not.

This paper presents a broadcasting algorithm that considerably reduces the number of retransmissions in applications such as onroad vehicular broadcasting where nodes are assumed to be arranged on a strip. Analysis and simulation results are presented to describe the overhead, coverage and latency characteristics of the algorithm.

We study the problem of coverage of a given area for a maximum duration using a set of battery-operated sensors. Each sensor has a fixed sensing range and a limited lifetime due to the finite battery capacity. Sensors can be activated and deactivated at any time. The goal of this paper is to a find a schedule, determining when to activate and deactivate each sensor, to maximize the time for which every point in the area is covered by at least one sensor. We present several algorithms for this problem and show experimental and theoretical evidences to their efficiency. We also present an algorithm for a new model of coverage, called weak coverage, that does not require each point of the region to be covered all times, as long as the regions that are not covered are small

Base station placement has significant impact on sensor network performance. Despite its significance, results on this problem remain limited, particularly theoretical results that can provide performance guarantee. This paper proposes a set of procedure to design (1 -- ε) approximation algorithms for base station placement problems under any desired small error bound ε > 0. It offers a general framework to transform infinite search space to a finite-element search space with performance guarantee. We apply this procedure to solve two practical problems. In the first problem where the objective is to maximize network lifetime, an approximation algorithm designed through this procedure offers 1 / ε2 complexity reduction when compared to a state-of-the-art algorithm. This represents the best known result to this problem. In the second problem, we apply the design procedure to address base station placement problem for maximizing network capacity. Our (1 -- ε) approximation algorithm is the first theoretical result on this problem.

This paper study two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network among a set of sensors each of which has a data stream to get to the base station. Subject to power constraints at the sensors, our goal is to locate the base station and establish a network in order to maximize the lifespan of the network. Second, we study optimal sensor placement problems for quality coverage of given domains cluttered with obstacles. We assume "line-of-site", sensors, that sense a point only if the straight segment connecting the sensor to this point (the "line-of-site") does not cross any obstacle. so obstacles occludes area from using line-of-site sensors, the goal is to minimize the number of sensors required in order to have each point "well covered" according to precise criteria (e.g., that each point is seen by two sensors that form at least angle a, or that each point is seen by three sensors that form a triangle containing the point).

An $(\alpha,\beta)$-covered object is a simply connected planar region c with the property that for each point $p\in\partial c$ there exists a triangle contained in c and having p as a vertex, such that all its angles are at least $\alpha>0$ and all its edges are at least $\beta\cdot{\rm \diam}(c)$-long. This notion extends that of fat convex objects. We show that the combinatorial complexity of the union of n $(\alpha,\beta)$-covered objects of "constant description complexity" is $O(\lambda_{s+2}(n) \log^2n\log\log n)$, where s is the maximum number of intersections between the boundaries of any pair of given objects, and $\lambda_s(n)$ denotes the maximum length of an $(n,s)$-Davenport--Schinzel sequence. Our result extends and improves previous results concerning convex $\alpha$-fat objects.

A compact body c in ℝd is κ-round if for every point p∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ>0, the combinatorial complexity of the union of n κ-round, not necessarily convex objects in ℝ3 (resp., in ℝ4) of constant description complexity is O(n2+ε) (resp., O(n3+ε)) for any ε>0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight.

Global positioning systems (GPS) and mobile phone networks are making it possible to track individual users with an increasing accuracy. It is natural to ask whether one can use this information to maintain social networks. Here each user wishes to be informed whenever one of a list of other users, called the user's friends, appears in the user's vicinity. In contrast to more traditional positioning based algorithms, the computation here depends not only on the user's own position on a static map, but also on the dynamic position of the user's friends. Hence it requires both communication and computation resources. The computation can be carried out either between the individual users in a peer-to-peer fashion or by centralized servers where computation and data can be collected at one central location. In the peer-to-peer model, a novel algorithm for minimizing the number of location update messages between pairs of friends is presented. We also present an efficient algorithm for the centralized model, based on region hierarchy and quadtrees. The paper provides an analysis of the two algorithms, compares them with a naive approach, and evaluates them using the IBM city simulator system.

Given a polygonal curve and a geometric graph, we describe an efficient algorithm to find a path in the graph which is most similar to the curve, using the well-known Fréchet distance for curves.

We present an O(nlog/sup 1+/spl epsiv// n)-time algorithm for computing the optimal robot motion that maintains line-of-sight visibility between a target moving inside a polygon with n vertices which may contain holes. The motion is optimal for the tracking robot (the observer) in the sense that the target either remains visible for the longest possible time, or it is captured by the observer in the minimum time when feasible. Thus, the algorithm maximizes the minimum time-to-escape. Our algorithm assumes that the target moves along a known path. Thus, it is an off-line algorithm. Our theoretical results for the algorithm's runtime assume that the target is moving along a shortest path from its source to its destination. This assumption, however is not required to prove the optimality of the computed solution, hence the algorithm remains correct for the general case.

Given a sequence of k polygons in the plane, a start point s, and a target point, t, we seek a shortest path that starts at s, visits in order each of the polygons, and ends at t. If the polygons are disjoint and convex, we give an algorithm running in time O(kn log (n/k)), where n is the total number of vertices specifying the polygons. We also extend our results to a case in which the convex polygons are arbitrarily intersecting and the subpath between any two consecutive polygons is constrained to lie within a simply connected region; the algorithm uses O(nk2 log n) time. Our methods are simple and allow shortest path queries from s to a query point t to be answered in time O(k log n + m), where m is the combinatorial path length. We show that for nonconvex polygons this "touring polygons" problem is NP-hard.The touring polygons problem is a strict generalization of some classic problems in computational geometry, including the safari problem, the zoo-keeper problem, and the watchman route problem in a simple polygon. Our new results give an order of magnitude improvement in the running times of the safari problem and the watchman route problem: We solve the safari problem in O(n2 log n) time and the watchman route problem (through a fixed point s) in time O(n3 log n), compared with the previous time bounds of O(n3) and O(n4), respectively.

No abstract available.

Phonetic speech retrieval is used to augment word based retrieval in spoken document retrieval systems, for in and out of vocabulary words. In this paper, we present a new indexing and ranking scheme using metaphones and a Bayesian phonetic edit distance. We conduct an extensive set of experiments using a hundred hours of HUB4 data with ground truth transcript and twenty-four thousands query words. We show improvement of up to 15% in precision compare to results obtained speech recognition alone, at a processing time of 0.5 Sec per query.

In proteomics 2-dimensional gel electrophoresis (2-DE) is a separation technique for proteins. The resulting protein spots can be identified by either using picking robots and subsequent mass spectrometry or by visual cross inspection of a new gel image with an already analyzed master gel. Difficulties especially arise from inherent noise and irregular geometric distortions in 2-DE images. Aiming at the automated analysis of large series of 2-DE images, or at the even more difficult interlaboratory gel comparisons, the bottleneck is to solve the two most basic algorithmic problems with high quality: Identifying protein spots and computing a matching between two images. For the development of the analysis software CAROL at Freie Universität Berlin we have reconsidered these two problems and obtained new solutions which rely on methods from computational geometry. Their novelties are: 1. Spot detection is also possible for complex regions formed by several “merged” (usually saturated) spots; 2. User-defined landmarks are not necessary for the matching. Furthermore, images for comparison are allowed to represent different parts of the entire protein pattern, which only partially “overlap”. The implementation is done in a client server architecture to allow queries via the Internet. We also discuss and point at related theoretical questions in computational geometry.

An (α, β)-covered object is a simply connected planar region c with the property that for each point p ∈ ∂c there exists a triangle contained in c and having p as a vertex, such that all its angles are at least α and all its edges are at least β ·diam(c)-long. This notion extends that of fat convex objects. We show that the com-binatorial complexity of the union of n (α, β)-covered objects of ‘constant description com-plexity ’ is O(λs+2(n) log 2 n log logn), where s is the maximum number of intersections between the boundaries of any pair of the given objects. 1

Investigates data structures obtained by a recursive partitioning of the input domain into regions of equal size. One of the most well-known examples of such a structure is the quadtree, which is used in this paper as a basis for more complex data structures; we also provide multidimensional versions of the stratified tree of P. van Emde Boas (1997). We show that, under the assumption that the input points have limited precision (i.e. are drawn from an integer grid of size u), these data structures yield efficient solutions to many important problems. In particular, they allow us to achieve O(log log u) time per operation for finding the dynamic approximate nearest neighbor (under insertions and deletions) and the exact online closest pair (under insertions only) in any constant dimension. They allow O(log log u) point location in a given planar shape or in its expansion (dilation by a ball of a given radius). Finally, we provide a linear-time (optimal) algorithm for computing the expansion of a shape represented by a quadtree. This result shows that the spatial order imposed by this regular data structure is sufficient to optimize the dilation by a ball operation.

Let ${\cal F}$ be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the $({\le}k)$-level of the arrangement $\A({\cal F})$ is $O(k^{3+\varepsilon}\psi({n/k}))$ for any $\varepsilon>0$, where $\psi (r)$ is the maximum complexity of the lower envelope of a subset of at most r functions of ${\cal F}$. This bound is nearly optimal in the worst case and implies the existence of shallow cuttings, in the sense of [J. Matousek, Comput. Geom., 2 (1992), pp. 169--186], of small size in arrangements of bivariate algebraic functions. We also present numerous applications of these results, including (i) data structures for several generalized 3-dimensional range-searching problems; (ii) dynamic data structures for planar nearest- and farthest-neighbor searching under various fairly general distance functions; (iii) an improved (near-quadratic) algorithm for minimum-weight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.

Article Free Access Share on Fly cheaply: on the minimum fuel-consumption problem Authors: Alon Efrat School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69982, Israel School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69982, IsraelView Profile , Sariel Har-Peled School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69982, Israel School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69982, IsraelView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 143–145https://doi.org/10.1145/276884.276900Online:07 June 1998Publication History 3citation209DownloadsMetricsTotal Citations3Total Downloads209Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article On the union of κ-curved objects Share on Authors: Alon Efrat Department of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel Department of Computer Science, Tel-Aviv University, Tel-Aviv 69978, IsraelView Profile , Matthew J. Katz Department of Mathematics and Computer Science, Ben-Gurion University of the Negev, Beer-Sheva S4105, Israel Department of Mathematics and Computer Science, Ben-Gurion University of the Negev, Beer-Sheva S4105, IsraelView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 206–213https://doi.org/10.1145/276884.276908Online:07 June 1998Publication History 9citation161DownloadsMetricsTotal Citations9Total Downloads161Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We prove a near-linear bound on the combutorial complexity of the union of n fat convex objects in the plane, each pair of whose boundaries cross at most a constant number of times.

Let A and B be two sets of n objects in R d , and let M be a (one-to-one) matching between A and B. Let min(M ), max(M ), and \\Sigma(M ) denote the length of the shortest edge, the length of the longest edge, and the sum of the lengths of the edges of M respectively. Bottleneck matching---a matching that minimizes max(M )---is suggested as a convenient way for measuring the resemblance between A and B. Several algorithms for computing, as well as approximating, this resemblance are proposed. The running time of all the algorithms involving planar objects is close to O(n 1:5 ). For instance, if the objects are points in the plane, the running time of the exact algorithm is O(n 1:5 log n). A semi-dynamic data-structure for answering containment problems for a set of congruent disks in the plane is developed. This data structure may be of independent interest. Next, the problem of finding a translation of B that maximizes the resemblance to A under the bottleneck matching criterion...

Let 3 be a collection of n bivariate algebraic functions of constant maximum degree.We show that the combinatorial complexity of the vertical decomposition of the 0, where @(~) is the maximum complexity of the lower envelope of a subset of at most ~functions of 7.This result implies the existence of shallow cuttings, in the sense of [3, 31], of small size in arrangements of bivariate algebraic functions.We also present numerous applications of these results, including: (i) data structures for several generalized threedimensional range searching problems; (ii) dynamic data structures for planar nearest and farthest neighbor searching under various fairly general distance functions; (iii) an improved (near-quadratic) algorithm for minimum-weight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.