Search Constraints
« Previous 
1  10 of 11

Next »
Number of results to display per page
Search Results

 Resource Type:
 Article
 Creator:
 Morin, Pat, Hurtado, Ferran, Bose, Prosenjit, and Carmi, Paz
 Abstract:
 We prove that, for every simple polygon P having k ≥ 1 reflex vertices, there exists a point q ε P such that every halfpolygon that contains q contains nearly 1/2(k + 1) times the area of P. We also give a family of examples showing that this result is the best possible.
 Date Created:
 20110401

 Resource Type:
 Article
 Creator:
 Bose, Prosenjit, Overmars, M., Wilfong, G., Toussaint, G., GarciaLopez, J., Zhu, B., Asberg, B., and Blanco, G.
 Abstract:
 We study the feasibility of design for a layerdeposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid causes the liquid to harden. In order to understand the power as well as the limitations of this manufacturing process better, we define a mathematical model of stereolithography (referred to as vertical stereolithography) and analyze the class of objects that can be constructed under the assumptions of the model. Given an object (modeled as a polygon or a polyhedron), we give algorithms that decide in O(n) time (where n is the number of vertices in the polygon or polyhedron) whether or not the object can be constructed by vertical stereolithography. If the answer is in the affirmative, the algorithm reports a description of all the orientations in which the object can be made. We also show that the objects built with vertical stereolithography are precisely those that can be made with a 3axis NC machine. We then define a more flexible model that more accurately reflects the actual capabilities of stereolithography (referred to as variableangle stereolithography) and again study the class of feasible objects for this model. We give an O(n)time algorithm for polygons and O(n log n) as well as O(n)time algorithms for polyhedra. We show that objects formed with variableangle stereolithography can also be constructed using another manufacturing process known as gravity casting. Furthermore, we show that the polyhedral objects formed by vertical stereolithography are closely related to polyhedral terrains which are important structures in geographic information systems (GIS) and computational geometry. In fact, an object built with variableangle stereolithography resembles a terrain with overhangs, thus initiating the study of more realistic terrains than the standard ones considered in geographic information systems. Finally, we relate our results to the area of grasping in robotics by showing that the polygonal and polyhedral objects that can be built by vertical stereolithography can be clamped by parallel jaw grippers with any positivesized gripper.
 Date Created:
 19970101

 Resource Type:
 Conference Proceeding
 Creator:
 Dujmović, Vida, De Carufel, JeanLou, Bose, Prosenjit, and Paradis, Frédérik
 Abstract:
 The wellseparated pair decomposition (WSPD) of the complete Euclidean graph defined on points in ℝ2 (Callahan and Kosaraju [JACM, 42 (1): 6790, 1995]) is a technique for partitioning the edges of the complete graph based on length into a linear number of sets. Among the many different applications of WSPDs, Callahan and Kosaraju proved that the sparse subgraph that results by selecting an arbitrary edge from each set (called WSPDspanner) is a 1 + 8/(s − 4)spanner, where s > 4 is the separation ratio used for partitioning the edges. Although competitive localrouting strategies exist for various spanners such as Yaographs, Θgraphs, and variants of Delaunay graphs, few localrouting strategies are known for any WSPDspanner. Our main contribution is a localrouting algorithm with a nearoptimal competitive routing ratio of 1 + O(1/s) on a WSPDspanner. Specifically, we present a 2local and a 1local routing algorithm on a WSPDspanner with competitive routing ratios of 1+6/(s−2)+4/s and 1+6/(s−2)+ 6/s + 4/(s2 − 2s) + 8/s2respectively.
 Date Created:
 20170101

 Resource Type:
 Conference Proceeding
 Creator:
 Morin, Pat and Bose, Prosenjit
 Abstract:
 We consider online routing strategies for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing strategies, one that works for all Delaunay triangulations and the other that works for all regular triangulations, (2) a randomized memoryless strategy that works for all triangulations, (3) an O(1) memory strategy that works for all convex subdivisions, (4) an O(1) memory strategy that approximates the shortest path in Delaunay triangulations, and (5) theoretical and experimental results on the competitiveness of these strategies.
 Date Created:
 19990101

 Resource Type:
 Conference Proceeding
 Creator:
 Peleg, David, Krizanc, Danny, Kirousis, Lefteris M., Kranakis, Evangelos, Kaklamanis, Christos, and Bose, Prosenjit
 Abstract:
 In wireless communication, the signal of a typical broadcast station is transmited from a broadcast center p and reaches objects at a distance, say, R from it. In addition there is a radius r, r < R, such that the signal originating from the center of the station is so strong that human habitation within distance r from the center p should be avoided. Thus every station determines a region which is an “annulus of permissible habitation". We consider the following station layout (SL) problem: Cover a given (say, rectangular) planar region which includes a collection of orthogonal buildings with a minimum number of stations so that every point in the region is within the reach of a station, while at the same time no building is within the dangerous range of a station. We give algorithms for computing such station layouts in both the oneand twodimensional cases.
 Date Created:
 19990101

 Resource Type:
 Conference Proceeding
 Creator:
 Bose, Prosenjit and Van Renssen, André
 Abstract:
 We present tight upper and lower bounds on the spanning ratio of a large family of constrained θgraphs. We show that constrained θgraphs with 4k2 (k≥ 1 and integer) cones have a tight spanning ratio of 1+2 sin(θ/2), where θ is 2 π/ (4k+2). We also present improved upper bounds on the spanning ratio of the other families of constrained θgraphs.
 Date Created:
 20140101

 Resource Type:
 Conference Proceeding
 Creator:
 Bose, Prosenjit, Maheshwari, Anil, Carmi, Paz, Smid, Michiel, and Farshi, Mohammad
 Abstract:
 It is wellknown that the greedy algorithm produces high quality spanners and therefore is used in several applications. However, for points in ddimensional Euclidean space, the greedy algorithm has cubic running time. In this paper we present an algorithm that computes the greedy spanner (spanner computed by the greedy algorithm) for a set of n points from a metric space with bounded doubling dimension in time using space. Since the lower bound for computing such spanners is Ω(n 2), the time complexity of our algorithm is optimal to within a logarithmic factor.
 Date Created:
 20081027

 Resource Type:
 Conference Proceeding
 Creator:
 Couture, Mathieu, Smid, Michiel, Maheshwari, Anil, Bose, Prosenjit, Carmi, Paz, and Zeh, Norbert
 Abstract:
 Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, there exists a t(k)spanner for P that has chromatic number at most k. We prove that t(2)∈=∈3, t(3)∈=∈2, , and give upper and lower bounds on t(k) for k∈>∈4. We also show that for any ε>∈0, there exists a (1∈+∈ε)t(k)spanner for P that has O(P) edges and chromatic number at most k. Finally, we consider an online variant of the problem where the points of P are given one after another, and the color of a point must be assigned at the moment the point is given. In this setting, we prove that t(2)∈=∈3, , , and give upper and lower bounds on t(k) for k∈>∈4.
 Date Created:
 20080827

 Resource Type:
 Conference Proceeding
 Creator:
 Dujmović, Vida, Wood, David, and Bose, Prosenjit
 Abstract:
 We prove that for all 0 ≤ t ≤ k and d ≥ 2k, every graph G with treewidth at most k has a 'large' induced subgraph H, where H has treewidth at most t and every vertex in H has degree at most d in G, The order of H depends on t, k, d, and the order of G. With t = k, we obtain large sets of bounded degree vertices. With t = 0, we obtain large independent sets of bounded degree. In both these cases, our bounds on the order of H are tight. For bounded degree independent sets in trees, we characterise the extremal graphs. Finally, we prove that an interval graph with maximum clique size k has a maximum independent set in which every vertex has degree at most 2k.
 Date Created:
 20051201

 Resource Type:
 Conference Proceeding
 Creator:
 Bose, Prosenjit, Howat, John, and Morin, Pat
 Abstract:
 The time required for a sequence of operations on a data structure is usually measured in terms of the worst possible such sequence. This, however, is often an overestimate of the actual time required. Distributionsensitive data structures attempt to take advantage of underlying patterns in a sequence of operations in order to reduce time complexity, since access patterns are nonrandom in many applications. Unfortunately, many of the distribution sensitive structures in the literature require a great deal of space overhead in the form of pointers. We present a dictionary data structure that makes use of both randomization and existing spaceefficient data structures to yield very low space overhead while maintaining distribution sensitivity in the expected sense.
 Date Created:
 20090914