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

Translating a regular grid over a point set

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2003年第1-2期25卷 21-34页

作者： Bose, P van Kreveld, M Maheshwari, A Morin, P Morrison, J Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Univ Utrecht Dept Comp Sci NL-3508 TB Utrecht Netherlands

We consider the problem of translating a (finite or infinite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if it contains k or more points of S. The main set of problems we study have to do with translating an infinite grid so that the number of k-occupied cells is maximized or minimized. For these problems we obtain running times of the form O(kn polylog (n)). We also consider the problem of translating a finite size grid, with m cells, in order to maximize the number of k-occupied cells. Here we obtain a running time of the form O(knm polylog (nm)). In solving these problems, we design a data structure T that maintains in O(log n) time per operation, a function f : R --> R under the following query and update operations where [a, b) is a continuous interval in R: 1. INSERT(T, a, b, delta): Increase the value of f (x) by delta for all x is an element of [a, b). 2. DELETE(T, a, b, delta): Decrease the value of f (x) by delta for all x is an element of [a, b). 3. MAX-COVER(): Return max{f (x): x is an element of R}. 4. MAX-COVER-WITNESS(): Return a value x* such that f (x*) = max{f (x): x is an element of R}. 5. MAX-IN(a, b): Returns max{f (x): x is an element of [a, b)}. 6. MAX-WITNESS-IN(a, b): Returns a value x* such that f (x*) = max{f (x): x is an element of [a, b)}. as well as the min counter-parts of these queries. (C) 2002 Published by Elsevier Science B.V.

关键词： dynamic data structure binary tree intervals lazy update facility location maintenance of functions

来源：评论

学校读者我要写书评

暂无评论

Listing the bonds of a graph in O(n)-delay

引用

DISCRETE APPLIED MATHEMATICS 2024年 348卷 105-121页

作者： Raffaele, Alice Rizzi, Romeo Uno, Takeaki Dept Mech Energy & Management Via Pietro Bucci-Cubo 46C I-87036 Arcavacata di Rende Italy Univ Verona Dept Comp Sci Str Le Grazie 15 I-37134 Verona Italy Natl Inst Informat 2-1-2 HitotsubashiChiyoda ku Tokyo 1018430 Japan

Given a connected graph G = (V, E), with n := |V| vertices and m := |E| edges, a cut can be represented as a bipartition {S, S} of the vertices or as the set of those edges in E having one endpoint in S and the other in S, denoted by 8G(S, S). A cut is minimal, or also called bond, if and only if the two induced subgraphs obtained by removing the edges in the cut are both connected. When the bond separates two given vertices s and t, we talk about s, t-bond. In this work, we consider the problems of listing all the bonds and listing all the s, t-bonds in a graph. These fundamental problems find application in many research areas, such as, beyond graph theory, network reliability, bioinformatics, and chemistry. The state-of-the-art algorithm exploits binary partition to output each s, t-bond in O(m) per bond, being thus classified as an O(m)-delay algorithm. Here we present two new algorithms to address these problems. The first one implements a slightly different branching strategy than the state of the art, though achieving the same complexity. Anyway, we can improve it by relying on dynamic data structures and amortized analysis, obtaining an algorithm that outputs a new bond in O similar to(n). By assuming only the two bond-shores are output for every bond, this is the first outputlinear algorithm listing bonds. In case we commit to explicitly providing the entire edge-set of every bond, the delay becomes O similar to(n) + |8G(S, S)|. (c) 2024 Elsevier B.V. All rights reserved.

关键词： Enumeration Graph theory Minimal cut Binary partition dynamic data structure Amortized analysis

来源：评论

学校读者我要写书评

暂无评论

dynamic MAINTENANCE OF PLANAR DIGRAPHS, WITH APPLICATIONS

引用

ALGORITHMICA 1990年第4期5卷 509-527页

作者： TAMASSIA, R PREPARATA, FP UNIV ILLINOIS COORDINATED SCI LABURBANAIL 61801

We show that a planarst-graphG admits two total orders on the setV∪E ∪F, whereV, E, andF are respectively the set of vertices, edges, and faces ofG, with |V| =n. Assuming thatG is to be dynamically modified by means of insertions of edges and expansions of vertices (and their inverses), we exhibit anO(n)-space dynamic data structure for the maintenance of these orders such that an update can be performed in timeO(logn). The discovered structural properties of planarst-graphs provide a unifying theoretical underpinning for several applications, such as dynamic point location in planar monotone subdivisions, dynamic transitive-closure query in planarst-graphs, and dynamic contact-chain query in convex subdivisions. The presented techniques significantly outperform previously known solutions of the same problems.

关键词： Planarst-graph Transitive closure Point location Contact-chain Planar subdivision dynamic data structure On-line algorithm

来源：评论

学校读者我要写书评

暂无评论

NEW RESULTS ON dynamic PLANAR POINT LOCATION

引用

SIAM JOURNAL ON COMPUTING 1992年第5期21卷 972-999页

作者： SIU, WC JANARDAN, R UNIV MINNESOTA DEPT COMP SCIMINNEAPOLISMN 55455

A point location scheme is presented for a dynamic planar subdivision whose underlying graph is only required to be connected. The operations supported include: reporting the name of the region containing a query point, inserting/deleting an edge, and inserting/deleting/moving a degree-2 vertex. The scheme uses O(n) space, has a worst-case query time of O(log2 n), and a worst-case update time of O(log n), where n is the number of vertices currently in the subdivision. Insertion (respectively, deletion) of an arbitrary k-edge chain inside a region can be performed in O(k log(n + k)) (respectively, O(k log n)) time in worst-case. The scheme outperforms the solutions given in works by Fries, Mehlhorn, and Naeher and by Overmars and also handles more general subdivisions than the schemes given in works by Preparata and Tamassia. The result is based on a new solution to a dynamic visibility problem for a set of tine segments in the plane that are nonintersecting, except possibly at endpoints. The scheme is then extended to speed up the insertion/deletion of a k-edge monotone chain to O(log2 n log log n + k) time (or O(log n log log n + k) time for an alternative model of input), but at the expense of increasing the other time bounds slightly. Additional results include a generalization to subdivisions consisting of algebraic segments of bounded degree and a persistent scheme that allows point location queries in the past and updates in the present.

关键词： COMPUTATIONAL GEOMETRY dynamic data structure PLANAR SUBDIVISION POINT LOCATION PRIORITY SEARCH TREES TREES OF BOUNDED BALANCE

来源：评论

学校读者我要写书评

暂无评论

External Memory Planar Point Location with Logarithmic Updates

引用

ALGORITHMICA 2012年第1-2期63卷 457-475页

作者： Arge, Lars Brodal, Gerth Stolting Rao, S. Srinivasa Seoul Natl Univ Sch Comp Sci & Engn Seoul 151744 South Korea Aarhus Univ MADALGO Ctr Mass Data Algorithm A Ctr Danish Natl Res Fdn Dept Comp Sci DK-8200 Aarhus N Denmark

Point location is an extremely well-studied problem both in internal memory models and recently also in the external memory model. In this paper, we present an I/O-efficient dynamic data structure for point location in general planar subdivisions. Our structure uses linear space to store a subdivision with N segments. Insertions and deletions of segments can be performed in amortized O(log(B) N) I/Os and queries can be answered in O(log(B)(2) N) I/Os in the worst-case. The previous best known linear space dynamic structure also answers queries in O(log(B)(2) N) I/Os, but only supports insertions in amortized O(log(B)(2) N) I/Os. Our structure is also considerably simpler than previous structures.

关键词： Planar point location External memory model I/O model Vertical ray shooting query dynamic data structure

来源：评论

学校读者我要写书评

暂无评论

dynamically Reconstructing Minimum Spanning Trees After Swapping Pairwise Vertices

引用

IEEE ACCESS 2019年 7卷 16351-16363页

作者： Fu, Zhang-Hua Chen, Si-Bo Ming, Yi-Fei Chen, Yong-Quan Lai, Xiang-Jing Chinese Univ Hong Kong Inst Robot & Intelligent Mfg Robot Lab Logist Serv Shenzhen 518172 Peoples R China Nanjing Univ Posts & Telecommun Inst Adv Technol Nanjing 210023 Jiangsu Peoples R China

The minimum spanning tree (MST) problem is a fundamental problem in computer science and operations research, which has many real-life network design applications. Given a graph G with n vertices and m edges, starting from an MST (denoted by T) covering a subgraph of G, it is usually needed to reconstruct a new MST after swapping two vertices v is an element of T and v' is not an element of T. For this purpose, the most popular choice is to reconstruct an MST from scratch, for which the current fastest algorithm (Kruskal's algorithm based on Fibonacci heap) requires a time complexity of O(m + n . log n), implying that a high time complexity of O(n(2)) . O(m + n . log n) is needed to evaluate all the O(n(2)) possible swapping-based moves. In order to evaluate these moves more efficiently, we integrate a series of dynamic techniques to develop a fast dynamic swap-vertex move operator, which significantly reduces the overall time complexity from O(n(2)) . O(m + n . log n) to O(n) . O(m . log n). We also strictly prove the correctness of the introduced method. Finally, we choose three well-studied Steiner/spanning tree problems as our test bed and carry out extensive experiments on 140 representative instances to show the effectiveness and efficiency of the proposed method. More importantly, as a general-purpose method, the dynamic swap-vertex move operator could be easily adapted to many other tree-related problems.

关键词： dynamic data structure Steiner/spanning tree problems swap-vertex move operator

来源：评论

学校读者我要写书评

暂无评论

A dynamic FIXED WINDOWING PROBLEM

引用

ALGORITHMICA 1989年第4期4卷 535-550页

作者： KLEIN, R NURMI, O OTTMANN, T WOOD, D UNIV WATERLOO DEPT COMP SCIDATA STRUCTURING GRPWATERLOO N2L 3G1ONTARIOCANADA

Given a point set in the plane and a fixed planar region (window) a window query consists of enumerating the points in a translate of the region. A recently presented result demonstrates that there is astatic data structure, of optimal size, that solves window queries for convex regions in optimal time. We give a data structure, of optimal size, that not only supports window queries in optimal time for, possibly nonconvex, polygonal windows, but also allows updating of the point set in optimal time.

关键词： Window query dynamic data structure Priority search trees Point set Optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

dynamically Allocated Bloom Filter-Based PIT Architectures

引用

IEEE ACCESS 2022年 10卷 28165-28179页

作者： Jang, Saeyoung Byun, Hayoung Lim, Hyesook Ewha Womans Univ Dept Elect & Elect Engn Seoul 03760 South Korea Myongji Univ Dept Elect Engn Yongin 17058 South Korea

As a key component in implementing Named data Networking (NDN), Pending Interest Table (PIT) requires an efficient exact-matching algorithm for a scalable and fast PIT lookup. A Bloom filter (BF) is a memory-efficient data structure for performing exact matching operations. In this paper, three different BF-based PIT architectures are proposed: PIT using functional Bloom filters (FBF-PIT), PIT using counting Bloom filters with return values (rCBF-PIT), and a refined rCBF-PIT with signatures (R-rCBF-PIT). The proposed BF-based PITs incrementally allocate a new BF for storing multiple incoming faces of Interest packets with the same content name. For a data packet lookup, the proposed PIT architectures simultaneously access every BF structure to find matching faces and delete the faces (i.e., matching Interest packet information). The functional Bloom filter (FBF) used in an FBF-PIT is a key-value data structure that stores values only without keys. However, because the number of non-reusable conflict cells in the FBF increases as the number of stored packets increases in the FBF-PIT, the indeterminable rate increases. To decrease the indeterminable rate, we propose the rCBF-PIT, which uses counting Bloom filters with return values (rCBFs), allowing reusable conflict cells. False positives for Interest packets lead to incorrect deletions that can cause false negatives for incoming data packets. Because most of the false positives occur in the first BF structure, we finally propose the R-rCBF-PIT, in which the first rCBF is replaced with an rCBF with a signature field. The proposed PITs also provide an aging mechanism using a valid bit and a hit bit for entry expiration. Simulation results show that rCBF-PIT and R-rCBF-PIT both reduce the indeterminable rate by more than 81% compared with FBF-PIT. The results also show that R-rCBF-PIT resolves false negatives caused by incorrect deletions by including the signature fields in the first rCBF.

关键词： Faces Information filters Matched filters Programming Indexes Hash functions Filtering algorithms Bloom filter dynamic data structure named data networking pending Interest table

来源：评论

学校读者我要写书评

暂无评论

A dynamic clinical dental relational database

引用

IEEE TRANSACTIONS ON INFORMATION TECHNOLOGY IN BIOMEDICINE 2004年第3期8卷 298-305页

作者： Taylor, D Naguib, RNG Boulton, S Coventry Univ Sch Math & Informat Sci BIOCORE Coventry CV1 5FB W Midlands England Coventry Hlth Author Dent Publ Hlth Dept Coventry CV1 2GQ W Midlands England

The traditional approach to relational database design is based on the logical organization of data into a number of related normalized tables. One assumption is that the nature and structure of the data is known at the design stage. In the case of designing a relational database to store historical dental epidemiological data from individual clinical surveys, the structure of the data is not known until the data is presented for inclusion into the database. This paper addresses the issues concerned with the theoretical design of a clinical dynamic database capable of adapting the internal table structure to accommodate clinical survey data, and presents a prototype database application capable of processing, displaying, and querying the dental data.

关键词： dental epidemiology dynamic data structure relational database application

来源：评论

学校读者我要写书评

暂无评论

AN INCREMENTAL RECONSTRUCTION METHOD FOR dynamic PLANAR POINT LOCATION

引用

INFORMATION PROCESSING LETTERS 1991年第2期37卷 79-83页

作者： TAMASSIA, R UNIV ILLINOIS COORDINATED SCI LABURBANAIL 61801

We present a fully dynamic technique for point location in triangulations that allows a tradeoff between query and update time, and can be used in conjunction with any of the known static point location data structures. Let S be a triangulation whose current number of vertices is n. We show that for any smooth nondecreasing integer function b(n) with 2 less-than-or-equal-to b(n) less-than-or-equal-to square-root-n, there exists a dynamic point location data structure for S with space O(n), query time O(log2n)/log b(n)), and update time O((log2n)b(n)/log b(n).

关键词： POINT LOCATION PLANAR SUBDIVISION TRIANGULATION dynamic data structure ONLINE ALGORITHM COMPUTATIONAL GEOMETRY ANALYSIS OF ALGORITHMS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：