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

42nd National Conference on Theoretical Computer Science

作者： Chen, Yinhua Li, Jianglin Wang, Wencheng Zhang, Tongquan Yunnan Minzu Univ Sch Math & Comp Sci Yuehua St 2929 Kunming 650504 Yunnan Peoples R China Yunnan Minzu Univ Sch Appl Technol Yuehua St 2929 Kunming 650504 Yunnan Peoples R China

ISBN: (纸本)9789819614899;9789819614905

In this paper, we consider the problem of 1-line minimum lambda-Steiner tree problem, denoted as the 1L-M(lambda)StT problem. Given a set X = {r(1), r(2),..., r(n)} of n points in the lambda-plane and a straight line l in R-2, we need to construct a Steiner tree T-l connecting the n points in X and the straight line l. The objective is to minimize the total cost of such a Steiner tree T-l, i.e.,min{Sigma(epsilon is an element of Tl) w(e) | T-l is the mentioned Steiner tree}, and if an edge e = uv is an element of T-l has both endpoints u and v lying on the line l, the weight is defined as w(e) = 0;Otherwise, it is defined as the distance of the two endpoints u and v in the lambda-plane. In particular, if all Steiner points in T-l are constrained to lie on the line l, the problem is denoted as the 1-line minimum lambda-spanning tree (1L-M lambda ST) problem. We present two main results. (1) By using the strategies of the sweep-line algorithm, we can design an exact algorithm in time O(lambda n log n) to solve the 1L-M lambda ST problem;(2) Using some properties of lambda-plane, we showed that our algorithm is a rho(lambda)-approximation algorithm for the 1L-M(lambda)StT problem, where rho(lambda) is inverse of the Steiner ratio in the lambda-plane.

关键词： sweep-line algorithm Approximation algorithm 1-line lambda-spanning tree 1-line lambda-Steiner tree

来源：评论

学校读者我要写书评

暂无评论

A fast and scalable bottom-left-fill algorithm to solve nesting problems using a semi-discrete representation

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2022年第3期300卷 809-826页

作者： Chehrazad, Sahar Roose, Dirk Wauters, Tony Katholieke Univ Leuven Dept Comp Sci Campus Leuven Leuven Belgium Katholieke Univ Leuven Dept Comp Sci Technol Campus Gent Leuven Belgium

We present a fast algorithm to solve nesting problems based on a semi-discrete representation of both the 2D non-convex pieces and the strip. The pieces and the strip are represented by a set of equidistant vertical line segments. The discretization algorithm uses a sweep-line method and applies minimal extensions to the line segments of a piece to ensure that non-overlapping placement of the segments, representing two pieces, cannot cause overlap of the original pieces. We implemented a bottom-left-fill greedy placement procedure, using an optimised ordering of the segments overlap tests. The C++ implementation of our algorithm uses appropriate data structures that allow fast execution. It executes the bottom-left-fill algorithm for typical ESICUP data sets in a few milliseconds, even when rotation of the pieces is considered, and thus provides a suitable 'building block' for integration in metaheuristics. Moreover, we show that the algorithm scales well when the number of pieces increases. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Cutting Nesting problems Semi-discrete representation Bottom-left-fill algorithm sweep-line algorithm

来源：评论

学校读者我要写书评

暂无评论

Discrete unit square cover problem

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2018年第6期10卷

作者： Basappa, Manjanna Das, Gautam K. Indian Inst Informat Technol Dharwad Dept Comp Sci & Engn Dharwad Karnataka India Indian Inst Technol Guwahati Dept Math Gauhati India

In this paper, we consider the discrete unit square cover (DUSC) problem as follows: given a set P of n points and a set S of m axis-aligned unit squares in R-2, the objective is (i) to check whether the union of the squares in S covers all the points in P, and (ii) if the answer is yes, then select a minimum cardinality subset S* subset of S such that each point. in P is covered by at least one square in S*. For the DUSC problem: (i) we propose a (2+ 4/k-2)-approximation algorithm, where k(> 2) is an integer parameter that defines a trade-off between the running time and the approximation factor of the algorithm. The running time of our proposed algorithm is O(km(k)n + nlogn). Our solution of the DUSC problem is based on a simple (1 + 2/k-2)-approximation algorithm for the subproblem strip square cover (SSC) problem, where all the points in P are lying within a horizontal strip of unit height. (ii) we also propose a 2-approximation algorithm, which runs in O(m(4)n) time. The 2-approximation algorithm is based on an algorithm for the subproblem SSC problem. The algorithm for the subproblem is developed using plane sweep and graph search traversal techniques. We also extend this algorithm to get 2-approximation result for the weighted DUSC problem where the squares are assigned weights, and the aim is to choose a subset S* subset of S such that each point in P is covered by at least one square in S* and the sum of the weights of squares in S* is minimized.

关键词： Approximation algorithms discrete unit square cover sweep-line algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for Answering Geo-Range Query

Algorithms for Answering Geo-Range Query

引用

IEEE Global Telecommunications Conference (GLOBECOM 2010)

作者： Zhang, Xi Wu, Kui Gao, Yong Univ Victoria Dept Comp Sci Victoria BC V8W 3P6 Canada Univ British Columbia Dept Comp Sci Okanagan BC V1V 1V5 Canada

ISBN: (纸本)9781424456383

In wireless sensor networks, we usually need to detect interesting events based on the information gathered from multiple sensors. One useful detection is to test whether or not the average sensory value within an area is larger than a given threshold. Such type of query is called geo-range query. It should report the geographic centers where the average value of nearby sensors is greater than a certain threshold. Answering geo-range query is nontrivial because we do not know in advance the satisfying geographic centers, which may not be necessarily the same as the locations of sensors. We develop two efficient algorithms: the brute-force search algorithm and the sweepline algorithm. The brute-force search algorithm uses exhaustive search to enumerate all possible satisfying sub-regions. Its time complexity is O(n(3)), where n is the number of sensor nodes. The sweep-line algorithm uses a virtual line sweeping top-down through the plane. The algorithm takes O(n(2) log n) running time, and still obtains exact solution to the problem.

关键词： brute-force search algorithm exhaustive search geo-range query geographic center search problems sweep-line algorithm wireless sensor network wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2009年第4期19卷 341-356页

作者： Gavrilova, Marina L. Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada

Driven by the industrial challenge of labeling maps for GIS applications, we investigate the problem of computing a map region P such that a rectangular axis-parallel label L of a given size can be placed in it. The map region to be labeled is in general a non-convex n-gon which may contain holes. We first derive a new practical algorithm based on the sweep-line technique that determines the com set of Maximum Inscribed Rectangles (MIRs) in P in O(nk), where k is the size of the output, for the case when the polygon sides have an axis-parallel orientation. After the set of MIRs has been found, any subsequent query on label L placement runs in only O(logn) time. We then provide an algorithm to convert the general case to the axis-parallel case. Extensive experimentation in both laboratory and industrial settings confirms that the developed method is practical and highly efficient for processing large GIS data sets.

关键词： Map labeling polygons with holes U-shape sweep-line algorithm set of maximum inscribed rectangles GIS

来源：评论

学校读者我要写书评

暂无评论

Exact, efficient, and complete arrangement computation for cubic curves

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2006年第1-2期35卷 36-73页

作者： Eigenwillig, Arno Kettner, Lutz Schoemer, Elmar Wolpert, Nicola Max Planck Inst Informat D-66123 Saarbrucken Germany Johannes Gutenberg Univ Mainz Inst Informat D-55099 Mainz Germany

The Bentley-Ottmann sweep-line method can compute the arrangement of planar curves, provided a number of geometric primitives operating on the curves are available. We discuss the reduction of the primitives to the analysis of curves and curve pairs, and describe efficient realizations of these analyses for planar algebraic curves of degree three or less. We obtain a complete, exact, and efficient algorithm for computing arrangements of cubic curves. Special cases of cubic curves are conics as well as implicitized cubic splines and Bezier curves. The algorithm is complete in that it handles all possible degeneracies such as tangential intersections and singularities. It is exact in that it provides the mathematically correct result. It is efficient in that it can handle hundreds of curves with a quarter million of segments in the final arrangement. The algorithm has been implemented in C++ as an EXACUS library called CUBIX. (c) 2005 Elsevier B.V. All rights reserved.

关键词： arrangements algebraic curves sweep-line algorithm robustness exact geometric computation

来源：评论

学校读者我要写书评

暂无评论

Exact, efficient, and complete arrangement computation for cubic curves

Exact, efficient, and complete arrangement computation for c...

引用

20th ACM Symposium on Computational Geometry

作者： Eigenwillig, Arno Kettner, Lutz Schoemer, Elmar Wolpert, Nicola Max Planck Inst Informat D-66123 Saarbrucken Germany Johannes Gutenberg Univ Mainz Inst Informat D-55099 Mainz Germany

关键词： arrangements algebraic curves sweep-line algorithm robustness exact geometric computation

来源：评论

学校读者我要写书评

暂无评论

A tutorial for designing flexible geometric algorithms

引用

algorithmICA 2002年第1期33卷 52-70页

作者： Kapoor, V Kühl, D Wolff, A datango AG D-10405 Berlin Germany Phaidros Software AG D-98693 Ilmenau Germany Ernst Moritz Arndt Univ Greifswald Inst Math & Informat D-17487 Greifswald Germany

The implementation of an algorithm is faced with the issues of efficiency, flexibility, and ease-of-use. In this paper we suggest a design concept that greatly increases the flexibility of an implementation without sacrificing ease-of-use and efficiency. We demonstrate the advantages of our concept through a C++ implementation of a simple rectangle-intersection algorithm, which follows the well-known sweep-line paradigm. We lead the reader. who should be familiar with C++ and its template mechanism. from a naive interface in a step-by-step guide to an interface offering full flexibility. The gain in flexibility can reduce the overall implementation effort by facilitating code reuse. Reusability in turn helps to achieve correctness simply because more users mean more testing. Though most of the ingredients of our concept have already been suggested elsewhere, to our knowledge this is the first time that they are applied vigorously in a geometric setting. We include a thorough experimental analysis on random and real-world data.

关键词： generic design Standard Template Library sweep-line algorithm computational geometry

来源：评论

学校读者我要写书评

暂无评论

Two- and three-dimensional ray tracing applied to the land mobile satellite (LMS) propagation channel

引用

IEEE ANTENNAS AND PROPAGATION MAGAZINE 2001年第6期43卷 27-37页

作者： Döttling, M Jahn, A Didascalou, D Wiesbeck, W Univ Karlsruhe TH Inst Hochfrequenztech & Elektron D-76128 Karlsruhe Germany German Aerosp Ctr DLR Inst Commun & Navigat D-82234 Oberpfaffenhofen Germany

This work examines the application of ray-tracing propagation models to system simulations for satellite mobile communications. A two-dimensional (2D) and a three-dimensional (3D) algorithm are outlined and compared using canonical propagation problems. Additional comparisons of both models with measurement campaigns are performed. The results show that two-dimensional models are suited for coverage and network planning. For system-design studies, however, three-dimensional ray tracing is mandatory. The novel three-dimensional ray-tracing model is able to predict time series of power delay profiles, Doppler and polarimetric information with high precision. It includes the time-variant correlation between the propagation channels of all visible satellites of an arbitrary satellite constellation. It therefore proves to be especially suited for system investigation of future LMS communication and navigation systems.

关键词： satellite mobile communication propagation ray tracing system simulation delay effects sweep-line algorithm

来源：评论

学校读者我要写书评

暂无评论

Two efficient algorithms for determining intersection points between simple polygons

引用

COMPUTERS & GEOSCIENCES 2000年第2期26卷 137-151页

作者： Zalik, B Univ Maribor Fac Elect Engn & Comp Sci SLO-2000 Maribor Slovenia

The paper describes two new algorithms for calculating the intersection points between two Simple (non-self-intersected) polygons. Both algorithms use a sweep-line approach and differ only in how they store the so-called sweep-line status. The first algorithm (set-based intersection algorithm) needs two one-way dynamic lists of currently pierced line segments, whereas the second algorithm (a binary-search-tree-based intersection algorithm) uses a binary search tree for this purpose. In the situation of the first algorithm, the theoretical time complexity is still O(k(2)) (k=n+m, where n and m are the number of the input polygons' vertices) whereas the second algorithm gives O((k+I) x log(2)(k+I)), where I is the number of intersection points between the polygon edges. However, as shown in the paper, the expected time complexity of the first algorithm is closer to the second algorithm than to the brute-force implementation. The importance of the presented algorithms in GIS applications is considered. Boolean operations, polygon interference determination, splitting a polygon by a polyline, merging the set of polygons and constructing the geometric buffers are briefly described. (C) 2000 Elsevier Science Ltd. All rights reserved.

关键词： simple polygon intersection points sweep-line algorithm computational geometry GIS applications

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：