Computing desk
< February 27	<< Jan \| February \| Mar >>	March 1 >

Welcome to the Wikipedia Computing 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.

February 28

Complexity Class/Average Time

Consider the following problem: you are given a set of n points in the plane and want to find the largest distance between two points. Does anyone know what the complexity class of this is? What the average time this can be found in is/worst time, etc.? Phoenix1177 (talk) 00:32, 28 February 2009 (UTC)[reply]

The distance between two points in 2D is sqrt((X₁-X₂)²+(Y₁-Y₂)²). To find the maximum distance in a set of points I would normally find the square of the distance between every point pair (plug them into the previous formula but omit the square root). This way the distances can be compared without the inefficient square root operation. Only once the maximum was found would it be necessary to do the square root to find the actual distance. This brute force approach could work well for up to thousands of points.

However, this approach wouldn't work so well if you had millions of points. This would require trillions of operations. In such a case, a more sophisticated approach would be needed. Perhaps a first pass could find the minimum X, maximum X, minimum Y, and maximum Y from the set of points. This could be used to find the center point. The square of the distance of every point from this center could then be found and maybe the farthest 1000 stored in a list. The farthest 2 points would likely be in this list, reducing processing time dramatically. I don't know if I could actually guarantee that the farthest two points would ALWAYS be found by this method, though. StuRat (talk) 04:56, 28 February 2009 (UTC)[reply]

The pair of points farthest away from each other (or one such pair, if it is not unique) will be guaranteed to be both on "corners" of the convex hull of the points. So one thing you can do is find the convex hull, which can be done in O(n log h) (where h is the number of points in the hull), and then kind of iterate around the hull on opposite sides at the same time, calculating the distances between points on the hull that are approximately "opposite" each other; this will take O(h), so this process is O(h + n log h), which is also O(n log n). --Spoon! (talk) 09:00, 28 February 2009 (UTC)[reply]

But how do you know if points are on opposite sides before you determine their distance ? StuRat (talk) 14:41, 28 February 2009 (UTC)[reply]

Thank you for the response, I had worked out an algorithim that used the fact that figuring out if a point in the plane was inside of a given square was very easy(since you just need to compare x and y with numbers defining the square) to use squares ever increasing in size to rule out pairs of points. It was quite better than the basic approach of calculating all the distances and then comparing them; but I'm fairly sure the convex hull approach works better, probably much better.

Relatedly, it is obvious that I can look at a bunch of dots on a page, draw a circle around one, measure the radius, and see what points aren't in it; thus, determining what points are less than r distance away from the center point. However, computers seem forced to manipulate the problem numerically; my point is that humans can do this quickly, and I don't think they'd have any problem, outside of listing all the points, even if the size of the set got very large; so, does anyone know if there is a way to get a computer to approach the problem geometrically in the sense of a human above, it should be possible. Ultimately, we can manipulate circles, mentally, by treating the circle like a single object, is there any language that can manipulate geometric objects in this fashion (without breaking them down into a representation of points in the plane, basically, that can do this elementally). Phoenix1177 (talk) 17:59, 28 February 2009 (UTC)[reply]

I see what you mean. There do seem to be some simple tasks which computers just can't do very well. Determining which points are inside a circle is one of them. Another common example is inserting something into the middle of a list. If I want to insert a shirt into a clothes rack, I just push the rest of the clothes back and pop it in. But computers can't do this without "taking every other item after the insertion point off the rack and placing it back onto the rack in the new position".

Back to the circle problem, you could convert the point coords all to polar coords, centered on that target point, which would then make determining which were inside a given radius trivial, but this would take just as long as calculating the distance to each.

Perhaps it would help if you could sort the points geometrically first. Say you have points with coords between -10 and 10 for both the X and Y coords. You could place all points with an X value between -10 and -9 and a Y value between 1 and 2 in one list, for example. If you then determined that this box is not worthy of further consideration, you could eliminate all the points contained therein at once, instead of making that determination for every point individually.

It would help if you could give some specifics, like exactly how many points there are and what range of X and Y coords they cover, and if any of the points will share the exact same coords, and if the points will be evenly distributed or clumped together. Also, what kind of response time is needed and do you need to be absolutely certain to get the maximum distance, or is a "close approximation" usable ? And don't overlook my suggestion of omitting the square root operation until the very end, as this makes an absolutely huge diff in performance. StuRat (talk) 20:31, 28 February 2009 (UTC)[reply]

This is from Introduction to Algorithms (by CLRS), page 948-949: (hopefully it is not a copyright violation to quote it here)

Consider, for example, the two-dimensional farthest-pair problem: we are given a set of n points in the plane and wish to find the two points whose distance from each other is maximum. As Exercise 33.3-3 asks you to prove, these two points must be vertices of the convex hull. Although we won't prove it here, the farthest pair of vertices of an n-vertex convex polygon can be found in O(n) time. Thus, by computing the convex hull of the n input points in O(n lg n) time and then finding the farthest pair of the resulting convex-polygon vertices, we can find the farthest pair of points in any set of n points in O(n lg n) time.

--Spoon! (talk) 21:37, 28 February 2009 (UTC)[reply]

Thank you again for your responses. As for specifics: I am not so much interested in this single problem, I am more interested in finding what methods are fast at solving geometric based problems, then seeing how these differ from the slower ones. The main intention being that I believe that there is a very large difference in how humans approach geometric problems, symbolic problems, computational problems, etc.; basically, I think there should exist ways to mechanize the ideas underlying these approaches in a way that would be useful. Phoenix1177 (talk) 21:49, 28 February 2009 (UTC)[reply]

I think many of the limitations in how computers approach such problems are due to them using linear programs and single processors (or small numbers). Perhaps a massive parallel array of processors could solve such machine vision problems like this (finding all the points within a circle) more quickly. For example, a program running on each processor could analyze whether each point is within a circle or not, so all points could be analyzed simultaneously. StuRat (talk) 16:07, 1 March 2009 (UTC)[reply]

I agree with what you're saying. However, I think that the way our minds represent data is important; consider the example of expanding a circle, we focus in on the radius increasing; or consider the case of a square, when translating it mentally we treat it as if it were a point, when compressing/expanding it we treat it like a set of four numbers corresponding to side lengths; etc. The point is that the representation/focus we use has a tendency to be naturally suited to the task at hand; obviously, this is because we have a visual system, but, the underlying representations should be capable of abstraction(I love wishful thinking...:) Phoenix1177 (talk) 12:00, 2 March 2009 (UTC)[reply]

Agreed. The points are never stored in our brains as a set of coords, for example, but are first stored with their relationship to other objects. In our case, that means they are initially stored as "points within the circle", so no further calculations are required. While our brains seem to have a single train of thought, much like a computer, I don't believe this applies to our senses, which do process all inputs simultaneously. So, we need to mimic both the massive parallel neural network in our brains and the storage structure used to record the results, if we want our computer to be as fast. StuRat (talk) 14:30, 2 March 2009 (UTC)[reply]

Windows XP wireless trouble

Maybe someone can help : / I recently installed Windows XP on my Macbook with Bootcamp, but for some reason, Windows XP refuses to recognize my wireless internet. It asks for a dial-up connection, but that's it. I looked through, I believe, all the menus and preferences etc, but I can't figure it out. Thanks! Evaunit♥666♥ 07:49, 28 February 2009 (UTC)[reply]

What service pack do you have installed? I have had trouble with the wireless internet on Service Pack 1 and lower. Also, it may just be that your installation of Windows does not have the drivers for your wireless NIC, most likely due to it being a Macbook. You could try searching for the driver on the internet on a friends' computer, download the driver, put said driver on a flash drive, and transfer to your macbook. You would need to know the model of your wireless NIC in order to do this though. Good luck. Until It Sleeps 02:05, 1 March 2009 (UTC)[reply]

Font used by Westboro Baptish Church

Can anyone tell me what fonts the Westboro Baptish Church uses for their signs? It doesn't look too exotic but I rarely recognise fonts. ----Seans Potato Business 18:11, 28 February 2009 (UTC)[reply]

WhatTheFont is usually very good indeed for this kind of thing. I found a large picture of WBC protesting on Google Images, cropped and rotated until I had a single line of text, and chucked it at WhatTheFont. It hasn't found the exact one (which seems to have slants on ascenders and descenders), but Eureka Sans Cont-Black Italic is kinda close. 87.113.105.126 (talk) 18:32, 28 February 2009 (UTC)[reply]

Replacing thumbnails with original image

Hi there, I'm looking for a way to use greasemonkey javascript to convert all links on a page from something like

website.com/thumb/001s.jpg
website.com/thumb/002s.jpg
website.com/thumb/003s.jpg
website.com/thumb/004s.jpg
etc

to

website.com/images/001.jpg
website.com/images/002.jpg
website.com/images/003.jpg
website.com/images/004.jpg

Please note that the image names I've given (001, 002, etc) are just examples and this would need to work for whatever the image name happened to be, and also not just for jpg but for png, gif, etc. So basically a page will load the full image instead of the thumbnail, but keep the image in the same size and placement on the page as the thumbnail. This is useful to me so that I can save a webpage and include the full images instead of having to download them individually later. Thank you so much to whoever can help me with this. Love xxx —Preceding unsigned comment added by 82.43.88.87 (talk) 19:28, 28 February 2009 (UTC)[reply]

If you're thinking of using this to download TGPs, you'll probably find it won't work. Too many have willfully weird schemes of doing things involving odd urls, links to subpages, javascript, and popup pages. You'll have as much or more luck with the Firefox plugin DownThemAll, but it founders on many of the same issues. 87.113.105.126 (talk) 19:44, 28 February 2009 (UTC)[reply]

The url layout I posted above is pretty much the same for each image with just the name of the jpg changing and the directory for /thumb/ and /images/ etc. I did find this which does exactly what I want on almost any page, but it loads the images all over the place and not in their original locations and thumbnailed size. I know it's asking a lot, but could anyone with some javascript skills possibly write something like this for what I want? I would be eternally grateful. Again, thank you —Preceding unsigned comment added by 82.43.88.87 (talk) 20:57, 28 February 2009 (UTC)[reply]

Alright, here's a snippet of javascript that presumably meets your requirements:

function img_fix() {

	for( var i = 0, j = document.getElementsByTagName('a'); j[i]; i++ ) {

		// if an anchor tag links to an image file and contains an image tag, use the link href for the image tag src
		

		if (j[i].href && j[i].href.match(/[.](bmp|gif|jpe?g|png|svg)/) && j[i].childNodes[0] && j[i].childNodes[0].src) {

			j[i].childNodes[0].src = j[i].href; 

		}

		// otherwise, check if an included image tag's src contains "thumb" and replace it with "images"

		else if (j[i].href && j[i].childNodes[0] && j[i].childNodes[0].src && j[i].childNodes[0].src.match(/thumb/)) {

			j[i].childNodes[0].src = j[i].childNodes[0].src.replace(/thumb(nail)?s?/,'images');
		}

	}
}


document.addEventListener('load',function addButton() {

	// throw a link up in the corner

	if( !document.body ) { return; }
	var mydiv = document.createElement('div');
	mydiv.style.position = 'fixed';
	mydiv.style.top = '0px';
	mydiv.style.right = '0px';
	mydiv.style.width = '20px';
	mydiv.style.border = '1px solid #000';
	mydiv.style.backgroundColor = '#fff';
	mydiv.style.color = '#000';
	mydiv.innerHTML = '<a href="javascript:img_fix();">fix</a>';
	document.body.appendChild(mydiv);

},false);

This code is intended (and tested) to run in Opera, but I'm sure it could be adapted to greasemonkey with a minimum of effort. You can modify the replace statement to handle URLs that don't quite fit your description. – 74 23:24, 28 February 2009 (UTC)[reply]

Incidentally, here are a couple pages that work with this script:

http://www.lacasahealth.net/pg_tech.html
http://www.solarturbinegroup.org/media/tech/ (it is necessary to disable automatic redirection)

– 74 15:24, 1 March 2009 (UTC)[reply]

You are a fucking hero for doing that for me! Unfortunately I can't seem to get it to work in greasemonkey, but thank you anyway for the time you put into that. While searching I came across this which does exactly what I want but only on coppermine galleries. If it's not too much to ask, could you have a look at that script and see if it could be adapted to my urls? Again, thank you, you deserve another barnstar!

Here is a greasemonkey equivalent script:

// ==UserScript==
// @name           Thumbnail Sourceror
// @namespace      http://userscripts.org/users/useridnumber
// @description    Attempt to replace all thumbnails with linked image content
// @include        *
// 
// ==/UserScript==
(function() {
	for( var i = 0, j = document.getElementsByTagName('a'); j[i]; i++ ) {

		// if an anchor tag links to an image file and contains an image tag, use the link href for the image tag src

		if (j[i].href && j[i].href.match(/[.](bmp|gif|jpe?g|png|svg)/) && j[i].childNodes[0] && j[i].childNodes[0].src) {

			j[i].childNodes[0].src = j[i].href;
		}

		// otherwise, check if an included image tag's src contains "thumb" and replace it with "images"

		else if (j[i].href && j[i].childNodes[0] && j[i].childNodes[0].src && j[i].childNodes[0].src.match(/thumb/)) {

			j[i].childNodes[0].src = j[i].childNodes[0].src.replace(/thumb(nail)?s?/,'images');
		}
	}
 })();

You'll probably want to turn this script off when you're not using it. – 74 19:55, 1 March 2009 (UTC)[reply]

YES! This is perfect thank you!!!!!! —Preceding unsigned comment added by 82.43.88.87 (talk) 20:49, 1 March 2009 (UTC)[reply]

Laptop Head to Head

Which one of these laptops is faster in terms of gaming performance and image/video processing?

The 2.4 Ghz MacBook Pro: http://www.futureshop.ca/catalog/proddetail.asp?logon=&langid=EN&sku_id=0665000FS10111222&catid=

Or the HP HDX 16t Premium series upgraded to the same price as the MacPro: http://www.shopping.hp.com/webapp/shopping/computer_series.do?storeName=computer_store&category=notebooks&series_name=HDX16t_series&a1=Category&v1=Performance%20and%20entertainment

Both are roughly around $2,000 CAD.

By looking at the technical specs, I'm assuming that the HP will give better performance right? If so, aside from styling, what does the MacBook Pro offer over the HP to justify its equivalent cost?

Acceptable (talk) 20:04, 28 February 2009 (UTC)[reply]

As far as I can tell, portability. Looking up reviews on the Google, the HP might have anywhere between 119 minutes and 156 minutes battery life in 'regular use' (that is, wifi, web browsing, not using the optical drive or doing 3D games); reviewers say the Macbook Pro will do ~300 minutes. The HP is also larger (14.9 x 10.0 x 1.7 inches vs. 0.95 x 14.35 x 9.82 inches) and heavier (7.3 lbs vs. 5.5 lbs). If you don't care about that stuff, that HP and other laptops will no doubt offer more value. -- Consumed Crustacean (talk) 00:23, 1 March 2009 (UTC)[reply]

Are the games you want to play available on Mac? Astronaut (talk) 20:26, 1 March 2009 (UTC)[reply]

That is relevant as well; you have to factor in the price of Windows if the games aren't on OS X (unless you have access to a copy of Windows, or wish to "acquire" it through other means). Apple also has this tendency to underclock their laptop GPUs to a degree, likely due to heat and/or power usage concerns. This will obviously cause some performance degredation. You can up the clockrate in Windows using tools like Rivatuner, but you risk overheating.

I played with the HP site, got a laptop at about the same equivalent price, but with 4GB of DDR2 RAM (compared to 2GB DDR3 in the MBP), a 320GB 7200rpm HDD (compared to 250GB 5400rpm), a 1920x1080 screen (vs. 1440 x 900), 2.53GHz Core 2 Duo (vs. 2.4GHz), a BD/DVD/CD drive (vs. DVD/CD), and the same 9600M GT GPU (the MBP also has the weaker 9400M which can be switched to in order to improve battery life). There's no doubt that this is better value if battery life and size/weight is of no concern. -- Consumed Crustacean (talk) 23:04, 1 March 2009 (UTC)[reply]

Freeware utility: Screenshots with Alpha Transparency

Is there really no freeware utility able to make screenshots of windows with an alpha channel? (Many Windows Vista screenshots on English Wikipedia have alpha transparency preserved.) --Andreas Rejbrand (talk) 20:08, 28 February 2009 (UTC)[reply]

Window Clippings is the only one I know of. It's not free any longer, though the old free versions can still be found. -- Consumed Crustacean (talk) 01:51, 1 March 2009 (UTC)[reply]

Thank you very much. I had been looking at Window Clippings, but didn't know that there were old freeware versions of it available! Thanks again! --Andreas Rejbrand (talk) 13:04, 1 March 2009 (UTC)[reply]

Resolved

OT: I don't get it. Why would one want to make screenshots with alpha, and where would such a thing occur? -- Fullstop (talk)

In Windows Vista, the frame around a window is not 100 % opaque, but slightly transparent. Thus, if you take a screenshot of a window using Windows ordinary "Print Screen" method, you will see what is behind the frame, which usually is not what you want. In addition, the frame is not perfectly rectangular, so even if you position the window in front of a white area on the screen, a few white pixels will be visible in the screenshot, which does not look very good against a black background. Therefore, one would like an application, such as Window Clippings, to copy only the pixels from the window alone, with the alpha channel preseved. See this example of the difference between an ordinary screenshot and one with alpha data preserved. --Andreas Rejbrand (talk) 21:25, 1 March 2009 (UTC)[reply]

Now I see that the alpha channel is still lost in the first example, but surely you get the point: if the page background were black, the first screenshot would look much better with its alpha channel. --Andreas Rejbrand (talk) 21:32, 1 March 2009 (UTC)[reply]

Also, if you would like to paste the screenshot (of a window) on a (larger) screenshot of a desktop, then, if it is going to look good, the content of the desktop must be slightly visible below the frame of the window. This is only possible to accomplish (reasonably easy) if the alpha transparency data is preserved in the screenshot. —Preceding unsigned comment added by Andreas Rejbrand (talk • contribs) 21:57, 1 March 2009 (UTC)[reply]