Misplaced Pages

#444555

50-402: Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O( n ) and O( n log n ) may be the difference between days and seconds of computation. The main impetus for the development of computational geometry as a discipline

100-399: A = log( t 2 / t 1 )/log( n 2 / n 1 ) . In other words, this measures the slope of the empirical line on the log–log plot of run-time vs. input size, at some size point. If the order of growth indeed follows the power rule (and so the line on the log–log plot is indeed a straight line), the empirical value of will stay constant at different ranges, and if not, it will change (and

150-448: A constant c , the run-time of that algorithm will never be larger than c × f ( n ) . This concept is frequently expressed using Big O notation. For example, since the run-time of insertion sort grows quadratically as its input size increases, insertion sort can be said to be of order O ( n ) . Big O notation is a convenient way to express the worst-case scenario for a given algorithm, although it can also be used to express

200-414: A constant factor, and in this sense all practical algorithms are O (1) for a large enough constant, or for small enough data. This interpretation is primarily useful for functions that grow extremely slowly: (binary) iterated logarithm (log ) is less than 5 for all practical data (2 bits); (binary) log-log (log log n ) is less than 6 for virtually all practical data (2 bits); and binary log (log n )

250-1866: A constant greater than or equal to [ T 1 .. T 7 ] T 6 ( n 2 + n ) + T 5 ( n 2 + 3 n ) + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ k ( n 2 + n ) + k ( n 2 + 3 n ) + k n + 5 k = 2 k n 2 + 5 k n + 5 k ≤ 2 k n 2 + 5 k n 2 + 5 k n 2   ( for  n ≥ 1 ) = 12 k n 2 {\displaystyle {\begin{aligned}&T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k\\=&2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\ ({\text{for }}n\geq 1)=12kn^{2}\end{aligned}}} Therefore [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ c n 2 , n ≥ n 0  for  c = 12 k , n 0 = 1 {\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1} A more elegant approach to analyzing this algorithm would be to declare that [ T 1 .. T 7 ] are all equal to one unit of time, in

300-418: A constant. One must be careful here; for instance, some analyses count an addition of two numbers as one step. This assumption may not be warranted in certain contexts. For example, if the numbers involved in a computation may be arbitrarily large, the time required by a single addition can no longer be assumed to be constant. Two cost models are generally used: The latter is more cumbersome to use, so it

350-411: A growth in the size of the input. Different inputs of the same size may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound , determined from the worst case inputs to the algorithm. The term "analysis of algorithms"

400-421: A mere reporting of the output. This lower bound is attainable, because several general-purpose convex hull algorithms run in linear time when input points are ordered in some way and logarithmic-time methods for dynamic maintenance of ordered data are well-known. This problem may be overcome by eliminating the restriction on the output representation. There are data structures that can maintain representations of

450-439: A program that looks up a specific entry in a sorted list of size n . Suppose this program were implemented on Computer A, a state-of-the-art machine, using a linear search algorithm, and on Computer B, a much slower machine, using a binary search algorithm . Benchmark testing on the two computers running their respective programs might look something like the following: Based on these metrics, it would be easy to jump to

500-774: A system of units chosen so that one unit is greater than or equal to the actual times for these steps. This would mean that the algorithm's run-time breaks down as follows: 4 + ∑ i = 1 n i ≤ 4 + ∑ i = 1 n n = 4 + n 2 ≤ 5 n 2   ( for  n ≥ 1 ) = O ( n 2 ) . {\displaystyle 4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\ ({\text{for }}n\geq 1)=O(n^{2}).} The methodology of run-time analysis can also be utilized for predicting other growth rates, such as consumption of memory space . As an example, consider

550-566: Is a theoretical classification that estimates and anticipates the increase in running time (or run-time or execution time) of an algorithm as its input size (usually denoted as n ) increases. Run-time efficiency is a topic of great interest in computer science : A program can take seconds, hours, or even years to finish executing, depending on which algorithm it implements. While software profiling techniques can be used to measure an algorithm's run-time in practice, they cannot provide timing data for all infinitely many possible inputs;

SECTION 10

#1733085920445

600-473: Is also known as geometric modelling and computer-aided geometric design (CAGD). Core problems are curve and surface modelling and representation. The most important instruments here are parametric curves and parametric surfaces , such as Bézier curves , spline curves and surfaces. An important non-parametric approach is the level-set method . Application areas of computational geometry include shipbuilding, aircraft, and automotive industries. Below

650-456: Is governed by the value of j, which iterates from 1 to i . On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body (step 6) consumes T 6 time, and the inner loop test (step 5) consumes 2 T 5 time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body (step 6) consumes 2 T 6 time, and

700-460: Is important in practice because the accidental or unintentional use of an inefficient algorithm can significantly impact system performance. In time-sensitive applications, an algorithm taking too long to run can render its results outdated or useless. An inefficient algorithm can also end up requiring an uneconomical amount of computing power or storage in order to run, again rendering it practically useless. Analysis of algorithms typically focuses on

750-795: Is less than 64 for virtually all practical data (2 bits). An algorithm with non-constant complexity may nonetheless be more efficient than an algorithm with constant complexity on practical data if the overhead of the constant time algorithm results in a larger constant factor, e.g., one may have K > k log ⁡ log ⁡ n {\displaystyle K>k\log \log n} so long as K / k > 6 {\displaystyle K/k>6} and n < 2 2 6 = 2 64 {\displaystyle n<2^{2^{6}}=2^{64}} . For large data linear or quadratic factors cannot be ignored, but for small data an asymptotically inefficient algorithm may be more efficient. This

800-469: Is only employed when necessary, for example in the analysis of arbitrary-precision arithmetic algorithms, like those used in cryptography . A key point which is often overlooked is that published lower bounds for problems are often given for a model of computation that is more restricted than the set of operations that you could use in practice and therefore there are algorithms that are faster than what would naively be thought possible. Run-time analysis

850-410: Is particularly used in hybrid algorithms , like Timsort , which use an asymptotically efficient algorithm (here merge sort , with time complexity n log ⁡ n {\displaystyle n\log n} ), but switch to an asymptotically inefficient algorithm (here insertion sort , with time complexity n 2 {\displaystyle n^{2}} ) for small data, as

900-399: Is running an algorithm with a much slower growth rate. Informally, an algorithm can be said to exhibit a growth rate on the order of a mathematical function if beyond a certain input size n , the function f ( n ) times a positive constant provides an upper bound or limit for the run-time of that algorithm. In other words, for a given input size n greater than some n 0 and

950-433: Is the dynamic problems , in which the goal is to find an efficient algorithm for finding a solution repeatedly after each incremental modification of the input data (addition or deletion input geometric elements). Algorithms for problems of this type typically involve dynamic data structures . Any of the computational geometric problems may be converted into a dynamic one, at the cost of increased processing time. For example,

1000-416: Is the list of the major journals that have been publishing research in geometric algorithms. Please notice with the appearance of journals specifically dedicated to computational geometry, the share of geometric publications in general-purpose computer science and computer graphics journals decreased. Analysis of algorithms In computer science , the analysis of algorithms is the process of finding

1050-507: Is to develop efficient algorithms and data structures for solving problems stated in terms of basic geometrical objects: points, line segments, polygons , polyhedra , etc. Some of these problems seem so simple that they were not regarded as problems at all until the advent of computers . Consider, for example, the Closest pair problem : One could compute the distances between all the pairs of points, of which there are n(n-1)/2 , then pick

SECTION 20

#1733085920445

1100-440: The computational complexity of algorithms —the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the size of an algorithm's input to the number of steps it takes (its time complexity ) or the number of storage locations it uses (its space complexity ). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to

1150-411: The kinetic convex hull , which studies similar problems for continuously moving points. Dynamic convex hull problems may be distinguished by the types of the input data and the allowed types of modification of the input data. It is easy to construct an example for which the convex hull contains all input points, but after the insertion of a single point the convex hull becomes a triangle. And conversely,

1200-453: The range searching problem may be converted into the dynamic range searching problem by providing for addition and/or deletion of the points. The dynamic convex hull problem is to keep track of the convex hull, e.g., for the dynamically changing set of points, i.e., while the input points are inserted or deleted. The computational complexity for this class of problems is estimated by: Some problems may be treated as belonging to either of

1250-412: The algorithm above, steps 1, 2 and 7 will only be run once. For a worst-case evaluation, it should be assumed that step 3 will be run as well. Thus the total amount of time to run steps 1-3 and step 7 is: The loops in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( n + 1 ) times, which will consume T 4 ( n + 1 ) time. The inner loop, on the other hand,

1300-431: The asymptotic performance, particularly at the elementary level, but in practical applications constant factors are important, and real-world data is in practice always limited in size. The limit is typically the size of addressable memory, so on 32-bit machines 2 = 4 GiB (greater if segmented memory is used) and on 64-bit machines 2 = 16 EiB. Thus given a limited size, an order of growth (time or space) can be replaced by

1350-467: The asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input. Big O notation , Big-omega notation and Big-theta notation are used to this end. For instance, binary search is said to run in a number of steps proportional to the logarithm of the size n of the sorted list being searched, or in O (log n ) , colloquially "in logarithmic time ". Usually asymptotic estimates are used because different implementations of

1400-435: The average-case — for example, the worst-case scenario for quicksort is O ( n ) , but the average-case run-time is O ( n log n ) . Assuming the run-time follows power rule, t ≈ kn , the coefficient a can be found by taking empirical measurements of run-time { t 1 , t 2 } at some problem-size points { n 1 , n 2 }, and calculating t 2 / t 1 = ( n 2 / n 1 ) so that

1450-403: The categories, depending on the context. For example, consider the following problem. In many applications this problem is treated as a single-shot one, i.e., belonging to the first class. For example, in many applications of computer graphics a common problem is to find which area on the screen is clicked by a pointer . However, in some applications, the polygon in question is invariant, while

1500-414: The conclusion that Computer A is running an algorithm that is far superior in efficiency to that of Computer B . However, if the size of the input-list is increased to a sufficient number, that conclusion is dramatically demonstrated to be in error: Computer A, running the linear search program, exhibits a linear growth rate. The program's run-time is directly proportional to its input size. Doubling

1550-429: The convex hull in an amount of time per update that is much smaller than linear. For many years the best algorithm of this type was that of Overmars and van Leeuwen (1981), which took time O(log n ) per update, but it has since been improved by Timothy M. Chan and others. In a number of applications finding the convex hull is a step in an algorithm for the solution of the overall problem. The selected representation of

Computational geometry - Misplaced Pages Continue

1600-438: The convex hull may influence on the computational complexity of further operations of the overall algorithm. For example, the point in polygon query for a convex polygon represented by the ordered set of its vertices may be answered in logarithmic time, which would be impossible for convex hulls reported by the set of it vertices without any additional information. Therefore, some research of dynamic convex hull algorithms involves

1650-406: The deletion of a single point may produce the opposite drastic change of the size of the output. Therefore, if the convex hull is required to be reported in traditional way as a polygon, the lower bound for the worst-case computational complexity of the recomputation of the convex hull is Ω ( N ) {\displaystyle \Omega (N)} , since this time is required for

1700-524: The first one. The run-time complexity for the worst-case scenario of a given algorithm can sometimes be evaluated by examining the structure of the algorithm and making some simplifying assumptions. Consider the following pseudocode : A given computer will take a discrete amount of time to execute each of the instructions involved with carrying out this algorithm. Say that the actions carried out in step 1 are considered to consume time at most T 1 , step 2 uses time at most T 2 , and so forth. In

1750-399: The following pseudocode which manages and reallocates memory usage by a program based on the size of a file which that program manages: In this instance, as the file size n increases, memory will be consumed at an exponential growth rate, which is order O (2 ) . This is an extremely rapid and most likely unmanageable growth rate for consumption of memory resources . Algorithm analysis

1800-1885: The highest-order term in any given function dominates its rate of growth and thus defines its run-time order. In this example, n is the highest-order term, so one can conclude that f ( n ) = O ( n ) . Formally this can be proven as follows: Prove that [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ c n 2 ,   n ≥ n 0 {\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}} [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ ( n 2 + n ) T 6 + ( n 2 + 3 n ) T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7   ( for  n ≥ 0 ) {\displaystyle {\begin{aligned}&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\\\leq &(n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ ({\text{for }}n\geq 0)\end{aligned}}} Let k be

1850-427: The inner loop test (step 5) consumes 3 T 5 time. Altogether, the total time required to run the inner loop body can be expressed as an arithmetic progression : which can be factored as The total time required to run the inner loop test can be evaluated similarly: which can be factored as Therefore, the total run-time for this algorithm is: which reduces to As a rule-of-thumb , one can assume that

1900-441: The input size doubles the run-time, quadrupling the input size quadruples the run-time, and so forth. On the other hand, Computer B, running the binary search program, exhibits a logarithmic growth rate. Quadrupling the input size only increases the run-time by a constant amount (in this example, 50,000 ns). Even though Computer A is ostensibly a faster machine, Computer B will inevitably surpass Computer A in run-time because it

1950-441: The latter can only be achieved by the theoretical methods of run-time analysis. Since algorithms are platform-independent (i.e. a given algorithm can be implemented in an arbitrary programming language on an arbitrary computer running an arbitrary operating system ), there are additional significant drawbacks to using an empirical approach to gauge the comparative performance of a given set of algorithms. Take as an example

2000-503: The line is a curved line)—but still could serve for comparison of any two given algorithms as to their empirical local orders of growth behaviour. Applied to the above table: It is clearly seen that the first algorithm exhibits a linear order of growth indeed following the power rule. The empirical values for the second one are diminishing rapidly, suggesting it follows another rule of growth and in any case has much lower local orders of growth (and improving further still), empirically, than

2050-598: The pair with the smallest distance. This brute-force algorithm takes O ( n ) time; i.e. its execution time is proportional to the square of the number of points. A classic result in computational geometry was the formulation of an algorithm that takes O( n log n ). Randomized algorithms that take O( n ) expected time, as well as a deterministic algorithm that takes O( n log log n ) time, have also been discovered. The core problems in computational geometry may be classified in different ways, according to various criteria. The following general classes may be distinguished. In

Computational geometry - Misplaced Pages Continue

2100-450: The point represents a query. For example, the input polygon may represent a border of a country and a point is a position of an aircraft, and the problem is to determine whether the aircraft violated the border. Finally, in the previously mentioned example of computer graphics, in CAD applications the changing input data are often stored in dynamic data structures, which may be exploited to speed-up

2150-444: The point-in-polygon queries. In some contexts of query problems there are reasonable expectations on the sequence of the queries, which may be exploited either for efficient data structures or for tighter computational complexity estimates. For example, in some cases it is important to know the worst case for the total time for the whole sequence of N queries, rather than for a single query. See also " amortized analysis ". This branch

2200-425: The problems of this category, some input is given and the corresponding output needs to be constructed or found. Some fundamental problems of this type are: The computational complexity for this class of problems is estimated by the time and space (computer memory) required to solve a given problem instance. In geometric query problems , commonly known as geometric search problems , the input consists of two parts:

2250-604: The same algorithm may differ in efficiency. However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor called a hidden constant . Exact (not asymptotic) measures of efficiency can sometimes be computed but they usually require certain assumptions concerning the particular implementation of the algorithm, called a model of computation . A model of computation may be defined in terms of an abstract computer , e.g. Turing machine , and/or by postulating that certain operations are executed in unit time. For example, if

2300-470: The search space part and the query part, which varies over the problem instances. The search space typically needs to be preprocessed , in a way that multiple queries can be answered efficiently. Some fundamental geometric query problems are: If the search space is fixed, the computational complexity for this class of problems is usually estimated by: For the case when the search space is allowed to vary, see " Dynamic problems ". Yet another major class

2350-417: The simpler algorithm is faster on small data. Dynamic convex hull The dynamic convex hull problem is a class of dynamic problems in computational geometry . The problem consists in the maintenance, i.e., keeping track, of the convex hull for input data undergoing a sequence of discrete changes, i.e., when input data elements may be inserted, deleted, or modified. It should be distinguished from

2400-442: The sorted list to which we apply binary search has n elements, and we can guarantee that each lookup of an element in the list can be done in unit time, then at most log 2 ( n ) + 1 time units are needed to return an answer. Time efficiency estimates depend on what we define to be a step. For the analysis to correspond usefully to the actual run-time, the time required to perform a step must be guaranteed to be bounded above by

2450-428: Was coined by Donald Knuth . Algorithm analysis is an important part of a broader computational complexity theory , which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem . These estimates provide an insight into reasonable directions of search for efficient algorithms . In theoretical analysis of algorithms it is common to estimate their complexity in

2500-921: Was progress in computer graphics and computer-aided design and manufacturing ( CAD / CAM ), but many problems in computational geometry are classical in nature, and may come from mathematical visualization . Other important applications of computational geometry include robotics ( motion planning and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated circuit design (IC geometry design and verification), computer-aided engineering (CAE) (mesh generation), and computer vision ( 3D reconstruction ). The main branches of computational geometry are: Although most algorithms of computational geometry have been developed (and are being developed) for electronic computers, some algorithms were developed for unconventional computers (e.g. optical computers ) The primary goal of research in combinatorial computational geometry

#444555