检索结果-内蒙古大学图书馆

Distributed Alarming in the On-Duty and Off-Duty Models

IEEE-ACM TRANSACTIONS ON NETWORKING 2016年第1期24卷 218-230页

作者： Bienkowski, Marcin Gasieniec, Leszek Klonowski, Marek Korzeniowski, Miroslaw Mans, Bernard Schmid, Stefan Wattenhofer, Roger Univ Wroclaw Inst Comp Sci PL-50383 Wroclaw Poland Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Wroclaw Univ Technol Inst Math & Comp Sci PL-50370 Wroclaw Poland Macquarie Univ Dept Comp Sydney NSW 2109 Australia Telekom Innovat Labs T Labs D-10587 Berlin Germany TU Berlin D-10587 Berlin Germany ETH Comp Engn & Networks Lab TIK CH-8000 Zurich Switzerland

Decentralized monitoring and alarming systems can be an attractive alternative to centralized architectures. Distributed sensor nodes (e. g., in the smart grid's distribution network) are closer to an observed event than a global and remote observer or controller. This improves the visibility and response time of the system. Moreover, in a distributed system, local problems may also be handled locally and without overloading the communication network. This paper studies alarming from a distributed computing perspective and for two fundamentally different scenarios: on-duty and off-duty. We model the alarming system as a sensor network consisting of a set of distributed nodes performing local measurements to sense events. In order to avoid false alarms, the sensor nodes cooperate and only escalate an event (i. e., raise an alarm) if the number of sensor nodes sensing an event exceeds a certain threshold. In the on-duty scenario, nodes not affected by the event can actively help in the communication process, while in the off-duty scenario, non-event nodes are inactive. We present and analyze algorithms that minimize the reaction time of the monitoring system while avoiding unnecessary message transmissions. We investigate time and message complexity tradeoffs in different settings, and also shed light on the optimality of our algorithms by deriving cost lower bounds for distributed alarming systems.

关键词： Disaster detection distributed algorithms distributed coordination output-sensitive algorithms neighborhood covers sensor networks

来源：评论

学校读者我要写书评

暂无评论

Refined notions of parameterized enumeration kernels with applications to matching cut enumeration

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 123卷 76-102页

作者： Golovach, Petr A. Komusiewicz, Christian Kratsch, Dieter Van Bang Le Univ Bergen Dept Informat N-5020 Bergen Norway Philipps Univ Marburg Fachbereich Math & Informat Marburg Germany Univ Lorraine LITA Metz France Univ Rostock Inst Informat Rostock Germany

An enumeration kernel as defined by Creignou et al. (2017) [11] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hardMatching Cutproblem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions. (C) 2021 The Author(s). Published by Elsevier Inc.

关键词： Enumeration problems Polynomial delay output-sensitive algorithms Kernelization Structural parameterizations Matching cuts

来源：评论

学校读者我要写书评

暂无评论

Computing immobilizing grasps of polygonal parts

引用

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2000年第5期19卷 467-479页

作者： van der Stappen, AF Wentink, C Overmars, MH Univ Utrecht Dept Comp Sci NL-3508 TB Utrecht Netherlands

We present the first algorithms for computing all placements of (frictionless) point fingers that put a polygonal part inform closure and all placements of point fingers that achieve second-order immobility of a polygonal part. Our algorithms run in O(n(2+epsilon) + K) and O(n(2) log(2) n + K) time in the case of form closure and second-order immobility, respectively, where n is the number of vertices of the polygon, K is the description size of the resulting set of finger placements, and a is an arbitrarily small constant. The basis of our algorithm is a translation of the problem into geometric searching problems, which are solved using efficient data structures. Our results can be extended to the problem of computing all placements of a line and two points that put a polygonal part inform closure. The resulting algorithm runs in O(n(2) log(2) n + K) time, where K is again the description size of the output.

关键词： grasps output-sensitive algorithms data structures geometry

来源：评论

学校读者我要写书评

暂无评论

Interviews 3D:: A platform for interactive handling of massive data sets

引用

IEEE COMPUTER GRAPHICS AND APPLICATIONS 2007年第6期27卷 48-59页

作者： Bruederlin, Beat Heyer, Mathias Pfuetzner, Sebastian Tech Univ Ilmenau D-98684 Ilmenau Germany

Interviews3D confronts the CAD data explosion problem with new approaches that let users process fully detailed 3D models in real time, even on standard PCs or 32-bit laptops. It has demonstrated efficiency in real-ti... 详细信息

关键词： clash detection digital mockup DMU out-of-core data handling output-sensitive algorithms real-time massive model rendering virtual reality

来源：评论

学校读者我要写书评

暂无评论

Scalable computational geometry in MapReduce

引用

VLDB JOURNAL 2019年第4期28卷 523-548页

作者： Li, Yuan Eldawy, Ahmed Xue, Jie Knorozova, Nadezda Mokbel, Mohamed F. Janardan, Ravi Univ Calif Riverside Riverside CA 92521 USA Univ Minnesota Twin Cities Minneapolis MN 55455 USA Univ Oxford Oxford England

Hadoop, employing the MapReduce programming paradigm, has been widely accepted as the standard framework for analyzing big data in distributed environments. Unfortunately, this rich framework has not been exploited for processing large-scale computational geometry operations. This paper introduces CG_Hadoop;a suite of scalable and efficient MapReduce algorithms for various fundamental computational geometry operations, namely polygon union, Voronoi diagram, skyline, convex hull, farthest pair, and closest pair, which present a set of key components for other geometric algorithms. For each computational geometry operation, CG_Hadoop has two versions, one for the Apache Hadoop system and one for the SpatialHadoop system, a Hadoop-based system that is more suited for spatial operations. These proposed algorithms form the nucleus of a comprehensive MapReduce library of computational geometry operations. Extensive experimental results run on a cluster of 25 machines over datasets of size up to 3.8B records show that CG_Hadoop achieves up to 14x and 115x better performance than traditional algorithms when using Hadoop and SpatialHadoop systems, respectively.

关键词： Computational Geometry MapReduce Hadoop output-sensitive algorithms Distributed Systems

来源：评论

学校读者我要写书评

暂无评论

Fast stabbing of boxes in high dimensions

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期246卷 53-72页

作者： Nielsen, F INRIA F-06902 Sophia Antipolis France Univ Nice F-06304 Nice France Univ Tokyo Tokyo Japan Univ Nice Sophia Antipolis Valrose France

We present in this paper a simple yet efficient algorithm for stabbing a set F of n axis-parallel boxes in d-dimensional space with c(F) points in output-sensitive lime O(dn log c(F)) and linear space. Let c*(F) and b*(F) be, respectively, the minimum number of points required to stab F and the maximum number of pairwise disjoint boxes of F. We prove that b*(F) less than or equal to c*(F) less than or equal to c(F) less than or equal to b*(F)(1+log(2) b*(F))(d-1). Since finding a minimal set of c*(F) points is NP-complete as soon as d > 1, we obtain a fast precision-sensitive heuristic for stabbing. F whose quality does not depend on the input size, In the case of congruent or constrained isothetic boxes, our algorithm reports, respectively, c(F)less than or equal to 2(d-1)b*(F) and c(F)= O-d(b*(F)) stabbing points, Moreover, we show that the bounds we get on c(F) are asymptotically tight and corroborate our results with some experiments. We also describe an optimal output-sensitive algorithm for findings a minimal-size optimal stabbing point-set of intervals. Finally, we conclude with insights for further research. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： computational geometry geometric combinatorial optimization output-sensitive algorithms

来源：评论

学校读者我要写书评

暂无评论

output-sensitive Computation of Force-Closure Grasps of a Semi-Algebraic Object

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2011年第3期8卷 495-505页

作者： Cheong, Jae-Sook Kruger, Heinrich van der Stappen, A. Frank Elect & Telecommun Res Inst Creat & Challenging Res Div Taejon 305700 South Korea Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands

We propose a technique which significantly simplifies the computation of frictionless force-closure grasps of a curved planar part P. We use a colored projection scheme from the three-dimensional wrench space to two-dimensional screens, which allows us to reduce the problem of identifying combinations of arcs and concave vertices of P that admit frictionless force-closure grasps, to colored intersection searching problems in the screens. We show how to combine this technique with existing intersection searching algorithms to obtain efficient, output-sensitive algorithms to compute all force-closure grasps of P, where at most four hard, frictionless point contacts exert exactly four wrenches on P . If the boundary of P consists of n algebraic arcs of constant complexity and m concave vertices, we show how to compute all force-closure grasps with: four contacts along four arcs in O (n(8/3) log(1/3) n + K) time;four contacts along three arcs in O(n(5/2+epsilon) + K) time;one contact at a concave vertex and two contacts along two arcs in O(n(2)m(1/2+epsilon) + K) time;one contact at a concave vertex and two contacts along a single arc in O(nm) or O(n(3/2+epsilon) + K) time (depending on the size of m);where epsilon is an arbitrarily small positive constant and K is the output size-that is, the number of combinations of arcs and vertices of each type, that actually admit frictionless force-closure grasps. Note to Practitioners-A force-closure grasp of an object is a grasp that can resist any external force applied to the object. In this paper, we present methods to report all force-closure grasps of a flat, curved object, using four (or fewer) hard, frictionless contacts. A naive, but time consuming approach to computing all force-closure grasps would be to consider all possible combinations of boundary features (i.e., arcs or vertices) and for each compute the grasps that can be achieved by placing contacts on those features. This wastes time by considering combinations

关键词： Computational geometry curved planar part force-closure grasp output-sensitive algorithms

来源：评论

学校读者我要写书评

暂无评论

Planar lower envelope of monotone polygonal chains

引用

INFORMATION PROCESSING LETTERS 2015年第12期115卷 962-964页

作者： Lu, Daniel L. Carnegie Mellon Univ Inst Robot Pittsburgh PA 15213 USA

A simple linear search algorithm running in O(n + ink) time is proposed for constructing the lower envelope of k vertices from m monotone polygonal chains in 2D with n vertices in total. This can be applied to output-sensitive construction of lower envelopes for n arbitrary line segments in optimal O(n logk) time, where k is the output size. Compared to existing output-sensitive algorithms for lower envelopes, this is simpler to implement, does not require complex data structures, and is a constant factor faster. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Computational geometry Upper envelope Lower envelope output-sensitive algorithms

来源：评论

学校读者我要写书评

暂无评论

On point covers of c-oriented polygons

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期263卷 17-29页

作者： Nielsen, F Sony Comp Sci Labs Tokyo 1410022 Japan

Let Y be any family of n c-oriented polygons of the two-dimensional Euclidean plane E-2, i.e., bounded intersection of halfplanes whose normal directions of edges belong to a fixed collection of c distinct directions. Let phi (Y) denote the packing number of Y, that is the maximum number of pairwise disjoint objects of Y. Let tau (Y) be the transversal number of Y, that is the minimum number of points required so that each object contains at least one of those points. We prove that tau (Y)less than or equal toG(2,c)phi (Y)log(2)(c-1)(phi (Y)+1), where G(2,c) is the Gallai number of pairwise intersecting c-oriented polygons. Our bound collapses to tau (Y) = O(G)(2, c)phi (Y)) if objects are more or less of the same size. We describe a t(n, c) + O(nc log phi (Y))-time algorithm with linear storage that computes such a 0-transversal, where t(n, c) is the time required to pierce pairwise intersecting c-oriented polygons. We provide linear-time algorithms t(n, c) = Theta (nc) for alpha -fat c-oriented polytopes, translates or homothets of E-d proving that G(2,c) = O(alpha)(d), G (2, c)less than or equal tod(d) and G(2,c)less than or equal to (3d(3/2))(d) respectively. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： computational geometry output-sensitive algorithms precision-sensitive heuristics transversal and packing numbers

来源：评论

学校读者我要写书评

暂无评论

Efficient rendering of multiresolution meshes with guaranteed image quality

引用

VISUAL COMPUTER 1999年第9期15卷 443-452页

作者： Klein, R Schilling, A Univ Tubingen GRIS Wilhelm Schickard Inst D-72076 Tubingen Germany

output-sensitive rendering algorithms have recently generated a lot of interest. The number of triangles describing a scene was once smaller than the number of pixels. The model size is now significantly larger;the screen resolution remains fairly constant. In view-dependent use of multiresolution models for output sensitivity, one determines the lowest resolution necessary for object parts for good images. Some approaches use cones of normal vectors for illumination-dependent selective refining. The drawback: using only the normal cone for detection is a poor criterion in problematic cases, leading to too much time-consuming refinement. We describe a new approach for better estimation of normal deviations between the various levels of detail. This provides accurate lighting with a minimum number of triangles. In view-dependend use of multiresolution models for output sensitivity, one determines the lowest possible resolution for each object part that still gives good images.

关键词： multiresolution modelling illumination-dependent refinement normal cone mesh simplification output-sensitive algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：