Wikipedia:Reference desk/Archives/Mathematics/2008 November 20

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 20

Smooth GPS track with time

A track is a time-based sequence of latitude, longitude and elevation. But a real track recorded by a GPS receiver often has noise. I tried GRASS and Chaiken's Algorithm to smooth the recorded track, but the time field is lost. Any ideas to keep it? Python eggs (talk) 09:41, 20 November 2008 (UTC)

Unless you want to keep the precise times you're talking about smoothing out a three dimensional line with time as the third dimension. Most types of splines will do that for you just as well. Dmcq (talk) 10:10, 20 November 2008 (UTC)

You're going to get some weird effects if you treat the position as two dimensional and travel more than a few hundred miles. It's still probably the best way to do it but keep that discrepancy in mind and try to compensate when you can .froth. (talk) 14:49, 21 November 2008 (UTC)

I would just replace each data point's spatial values with the average of those for n original data points centered in time on the point. The "right" (odd) value of n will depend on your data; more noise will demand a larger n, but those will tend to contract circles in the motion and lose more data from the ends (where (n-1)/2 values can't be smoothed due to lack of neighbors). --Tardis (talk) 19:32, 26 November 2008 (UTC)

Summation

Hello. My problem borders on being homework but since I've done it and got the right answer, I think I'm abiding by the rules. I had to determine

$\sum _{n=1}^{\infty }n{2^{-n}}\,\!$

After some struggle, I eventually just wrote out the first six or so terms and summed the expression to n=1, 2 ... 6 and managed to express the fraction in a way that showed the sum to be 2. Job done.

I'm not terribly happy about this method though; I think it's because I like it when the algebra alone will be enough to find the solution without than having to put numbers in. Is there a better way?

Just so you know, I know how to sum a geometric series to infinity and how to sum arithmetic and geometric series to n. Thanks 92.3.227.143 (talk) 17:44, 20 November 2008 (UTC)

You know that $\sum x^{n}=1/(1-x)$. Differentiate both sides and see what happens. Fredrik Johansson 17:55, 20 November 2008 (UTC)

Of course, that requires you to differentiate an infinite series term by term, which requires uniform convergence. On a small enough disc, that series does converge uniformly (and that disc can include x=1/2), so it works, but to be rigorous you do need to check it. --Tango (talk) 18:51, 20 November 2008 (UTC)

Try dividing the series by 2 and subtracting the result from the original series and, as the previous poster says, see what happens. Dmcq (talk) 18:42, 20 November 2008 (UTC)

Or square the plain geometric series (the one without n), and see what happens. You may try the squaring operation first with finitely many terms of it. (Disclaimer. When we say "and see what happens" we implicitly mean you should leave your seat, protect your body under a shelter like e.g. a solid piece of furniture, count to twenty and then go and see what's happened. However, this Reference desk will not be responsible of any subsequent damage or injury)--PMajer (talk) 20:02, 20 November 2008 (UTC)

There are a number of ways to find this sum. Here's one:

${\begin{aligned}\sum _{n=1}^{\infty }n2^{-n}&=\sum _{n=1}^{\infty }(\,\underbrace {2^{-n}+\cdots +2^{-n}} _{n{\text{ terms}}}\,)\\&=\underbrace {{}\quad 2^{-1}\quad {}} _{\text{1 term}}\\&+\underbrace {{}\quad 2^{-2}+2^{-2}\quad {}} _{\text{2 terms}}\\&+\underbrace {{}\quad 2^{-3}+2^{-3}+2^{-3}\quad {}} _{\text{3 terms}}\\&+\underbrace {{}\quad 2^{-4}+2^{-4}+2^{-4}+2^{-4}\quad {}} _{\text{4 terms}}\\&+\cdots \end{aligned}}$

Now sum the numbers in the leftmost vertical column, getting 1.
Then sum the numbers in the next vertical column, getting 1/2.
Then sum the numbers in the next vertical column, getting 1/4.
And so on.
Then find the sum of those sums: 1 + 1/2 + 1/4 + .... Michael Hardy (talk) 22:55, 21 November 2008 (UTC)

Constructing a specific finite state automaton

I'm trying to construct a minimal finite state automaton recognising a language $L$, on an alphabet $X=\left\{a,b,c\right\}$, where L is the set of words on X that do not contain any of the words from a finite language, A, say, as subwords. For instance, if the word abc was in A, L would not contain any words which contained the string/subword abc. I've had some luck building automata where A is suitably small, but haven't managed to come up with a general method for construction. The case I'm trying to solve currently has A containing 12 words, the longest of which has 19 letters in it, and trial and error has ended up with me crouching over four A4 sheets stuck together, with edges and states as far as the eye can see.

I've tried sketching out the 'bare bones' of what the automaton would look like - I started out at the state just before each 'bad' subword, and worked backwards to the empty word (so, if abcbca was a bad subword, I would add as a branch out from the empty word: $1{\xrightarrow {a}}a{\xrightarrow {b}}ab{\xrightarrow {c}}abc{\xrightarrow {b}}abcb{\xrightarrow {c}}abcbc$), and then somehow loop back to earlier in the automaton (i.e. nearer the empty word), thus producing every word not containing the bad subwords. Even with this 'skeleton' though, I still have no idea what to do with the edges that branch off from each state of the 'skeletal routes' I've mapped out.

I know that if B, the set containing words on X which do contain the words in A as subwords, is regular, then $L=X^{*}\setminus B$ is regular, and I have a method for constructing this...but that leaves the problem of building an automaton that recognises B. I've only starting studying automata recently, so I'm not sure how difficult this problem is. Somehow proving that an language L for a set A is not regular would also be just as good (if disappointing) solution to the problem! Thanks a lot, 81.102.34.92 (talk) 18:14, 20 November 2008 (UTC)

Isn't it enough to solve the case when A is just one word (which is easy), and then take a sort of cartesian product of machines to solve the general case? That won't necessarily be minimal, but at least it'll work. I've never studied this stuff, so I could just be confused. Algebraist 18:39, 20 November 2008 (UTC)

This is where I throw in some of the particulars of the situation: in short, I'm trying to tessellate the Poincare disk, with a particular triangle, with a, b and c the reflections (as Moebius transformations) in its three sides. I'm searching for an algorithm which will draw each triangle once and only once (using PostScript, so it's all fairly rudimentary) - hence why I need the automaton to be minimal. So, for instance, I don't want to draw the triangle corresponding to the transformation aa, since that's just the same as the original ('identity') triangle.

Strictly, I'm looking to draw (once and only once) the triangle associated with each member of the group $\left\langle a,b,c:a^{2}=b^{2}=c^{2}=(ab)^{2}=(bc)^{3}=(ca)^{7}=1\right\rangle$ (i.e. the group generated by reflections in the side of the hyperbolic triangle with angles pi by (2, 3 and 7). The first attempt I mentioned in the OP used the relations in this group presentation to give, on top of the three involutions, $ba=ab$, $bcb=cbc$ and $cacacac=acacaca$ - I managed to produce an automaton excluding all words containing the left hand side of these equalities as subwords, however it turns out there are more complicated relations than just these six. I used GAP to find another six, which I tried and fail to work into the automaton. I managed to cobble together some code, in the end, which tested each word for the bad subwords, and only drew the triangle if none were present, but it was a bit laborious, and not as elegant nor as efficient as having the minimal automaton 81.102.34.92 (talk) 23:26, 20 November 2008 (UTC)

It'd probably be easiest to just find pre-existing software that does what you want. For example, look at [this paper] by Paul Gunnells (Figure 1 looks like what you were describing)... if I recall correctly, Gunnells has postscript code to do what you want (a friend of mine used such software, and I believe Gunnells gave it to her). [This] describes the construction of some software to do such calculations efficiently, in case you're looking for ideas for yourself, but it was written in a higher level language; and your best bet may be [this] which is that software itself. Check out its [sample output]. Eric. 131.215.158.179 (talk) 00:36, 21 November 2008 (UTC)

I recommend the existing postscript solutions (I don't remember which one, but this was actually where I learned to program in postscript and when I first failed to learn combinatorial group theory). However, I wanted to mention that GAP comes with a package called KBMAG that constructs the minimal dfsa of automatic groups.

gap> f:=FreeGroup(3);;
gap> g:=f/[f.1^2,f.2^2,f.3^2,(f.1*f.2)^2,(f.2*f.3)^3,(f.3*f.1)^7];;
gap> r:=KBMAGRewritingSystem(g);;
gap> AutomaticStructure(r);;
gap> NumberOfStatesFSA(WordAcceptor(r));
23

I think you also need to be concerned with efficiency in producing the words if you actually want to execute the postscript on a printer. The (word acceptor) automaton itself is likely quite small, but you may also need to worry about iterating over exponentially many words (low memory cost, but too much cpu cost). At any rate, look at KBMAG to get the automaton, kbmag manual. JackSchmidt (talk) 04:56, 21 November 2008 (UTC)

Actually the growth function is reasonably small, only O(n*n) words of length n, so you might keep track of the reduced words, and only append as necessary. I'm assuming you want a breadth first search. You could do a depth first search pretty easily though in postscript, and that might eliminate all the worries. If I recall correctly, my old solution was to use a C program to generate reduced words, and then cleverly define some postscript functions so that the reduced words were valid programs. The resulting postscript file is just a dataset really, rather than a program, so it is not quite as nice, but it could actually be printed on the printers available at the time. JackSchmidt (talk) 06:03, 21 November 2008 (UTC)

Thanks a lot, I'll have a look through this stuff - some of it looks promising. I don't particularly want to 'cheat' and use pre-existing software to produce the tessellation, though - I'd like to work through it myself (unless this proves infeasible), and hopefully learn something about areas I've never worked in before. Oh, and I don't need to worry particularly about the code not being executable by a printer; I've got a counter built it, which terminates the algorithm when the words being drawn reach a specified length. Thanks again, 81.102.34.92 (talk) 14:10, 22 November 2008 (UTC)

Your idea about attacking B is the right one; the trick is to start with an NFA that accepts it. This is easy: draw your skeleton for each element of A (sharing states when there are common affixes will help later, but isn't necessary), and make the last state of each skeleton a common accepting state that loops back to itself for all characters. Finish the NFA by adding an arc back to the start from every single state for every letter (or for ε if you like); this lets the machine recognize the forbidden words wherever they start. Then turn the NFA into a DFA (see powerset construction). Note that every single set will contain the start state, and that you need not distinguish between different sets that contain the accepting state, since the NFA is never compelled to leave that state and so all DFA states reachable from any DFA state that contains it will still contain it and be accepting. Finally, complement the DFA by making all accepting states unaccepting and vice versa. (This is trivial here: there's only the one accepting state, so turn it into a trap state, or delete it entirely if you like, following the rule that crashed machines reject. All other states become accepting.) --Tardis (talk) 19:31, 24 November 2008 (UTC)

PS – The order here is important: NFA(B) → DFA(B) → DFA(X*-B) is easy, but NFA(B) → NFA(X*-B) is difficult because NFAs are asymmetric and "want" to accept strings. --Tardis (talk) 19:34, 24 November 2008 (UTC)

This is just the automaton constructed by the Knuth-Morris-Pratt algorithm. In particular, the targets for the back links are given by the KMP failure function. In a nutshell, if you are at a state given by string "s", and you receive a character "c" that is not the correct next character you are looking for, then the back link target is going to be the longest prior state string "t" having the property that "t" is a suffix of "sc". -- Four Dog Night (talk) 03:21, 25 November 2008 (UTC)

Sorry, I didn't see that you have a set of words A instead of just one word. However, the construction is still basically the same. The set of states in your DFA is the set of prefix substrings of words in A, including the empty string, but not the full words of A. A trap state is added as well. Then at state "s", with next input "c", if "sc" is a word in A, then go to the trap state. If "sc" is not a word in A, then go to the maximal suffix substring of "sc" that is a state of the DFA. -- Four Dog Night (talk) 03:32, 25 November 2008 (UTC)

Bounding Box

Does a bounding box of area zero contain any points? For example, a bounding box with no width, no height, or both. For context, this is for a mapping application, but I'd like to know the general cases as well. Thanks in advance! --157.127.124.15 (talk) 20:02, 20 November 2008 (UTC)

I've never heard the term before, but judging by our article, any bounding box for a set of points by definition contains at least those points (and indeed their convex hull), so any bounding box for a nonempty set is itself nonempty. Algebraist 20:08, 20 November 2008 (UTC)

How about a rectangle, instead of a bounding box? --157.127.124.15 (talk) 20:12, 20 November 2008 (UTC)

I suppose whether the empty set counts as a rectangle depends on exactly how you define rectangle. I'd go with no. What do you want to know this for anyway? Algebraist 20:20, 20 November 2008 (UTC)

I'm trying to determine the proper way to implement an algorithm for determining whether a latitude/longitude point exists within a bounding box defined by four latitude/longitude points. One case I need to deal with is when all four bounds are 0,0, and there are points at 0,0. I'd prefer that, in this case, the bounding box doesn't contain the items at 0,0. It'd strengthen my argument to implement the algorithm this way if the math backed me up. Maybe (okay, probably) I'm splitting hairs. --157.127.124.15 (talk) 20:37, 20 November 2008 (UTC)

I guess it's just a matter of definition - it depends on whether the bounding box is defined in terms of $<$ or $\leq \,\!$. If you choose the former, then the box in your example would be empty. --Tango (talk) 21:31, 20 November 2008 (UTC)

For computer graphics it's quite common to define bounding boxes with each range closed-open e.g. 0≤x<1, 0≤y<1. if the bounds are the same then there's no points in the box. If you had it closed-closed then it would contain a point. The advantage of doing it closed-open is if an operation is tiled it doesn't apply to the edge or corner points twice. Dmcq (talk) 00:05, 21 November 2008 (UTC)

Half-closed can be nice for csg, but in the end the bounding box does not contain all vertices of the object it is bounding. That is usually bad. If you want to have the ability to define empty bounding boxes, use a flag. You will need special case code for almost all operations on empty boxes anyways. Another tip: store the four bounding box limits, do not replace two by the size. This gives you rounding error free boolean operations on the boxes. —Preceding unsigned comment added by 84.187.58.155 (talk) 00:11, 23 November 2008 (UTC)