Talk:Point location

Talk:Point location/Archive 1

Mouse click location

Mouse click ilocation is not an instance of point location in planar subdivision. No one in sane mind will formulate it in this way (I will not go into detail). The added footnote to Bern (rightly) considers it as a special case of hidden surface removal. Quoting: Typically windowed systems are used on workstations equipped with a mouse. Mouse-clicks switch the keyboard input stream from one window to another, so a fundamental problem is to locate the window containing a given mouse-click, that is, which rectangle is the highest along a given line of sight.

Please do not restore the questioned statement without discussion. - Altenmann >talk 16:53, 13 August 2023 (UTC)

You omitted the other key quote: "Algorithms for point location in the visible scene are also given." That is, in the abstract of the paper, this part of the paper is described explicitly as being an instance of point location. —David Eppstein (talk) 17:16, 13 August 2023 (UTC)

No it is not. Our article writes: In its most general form, the problem is, given a partition of the space into disjoint regions, to determine the region where a query point lies. Therefore the following sentence "As an example application" is false. I see a huge difference between "a partition of the space into disjoint regions" and "visible scene". Please provide a reference where the mouse click location is stated as a problem of location within "a partition of the space into disjoint regions". Altenmann >talk 17:21, 13 August 2023 (UTC)

If you see a huge difference between the abstract's description of the problem and the description of the same problem in the text of the article, then you do not understand this material and should not be editing the article. It is very common in computational geometry for problems to have multiple equivalent formulations, sometimes involving instances of different dimensions. This is an example of that phenomenon. —David Eppstein (talk) 17:29, 13 August 2023 (UTC)

Formulating mouse click location as point location in planar subdivision is not only a sloppiness, but also a disservice to students and practitioners in computer graphics, who would be directed to a wild-goose chase by this example. Therefore I am insistent. - Altenmann >talk 17:28, 13 August 2023 (UTC)

Maybe you need to be referred to User:Jnc/Astronomer vs Amateur.

The advantage of this example, making it lead-worthy, is that it describes a familiar and common situation where point location is really needed. The disadvantage is that general-purpose point location data structures are unlikely to be the right implementation choice for this specific situation. The usual example I give instead in my classes as motivation for point location is the locus method (solving other data structure query problems by building a subdivision and then doing point location in it, such as doing nearest neighbor search by point location in a Voronoi diagram) but that has the disadvantage of being much more technical. —David Eppstein (talk) 17:30, 13 August 2023 (UTC)

Please avoid personal attacks. Not to say that you misapplied the essay. The joke of the essay is the amateur demands a citation that states that "something is not X". I am asking for a citation for "something is X". - Altenmann >talk 17:39, 13 August 2023 (UTC)

I'm tempted to label what you just said a brilliant piece of intentional self-parody, Alenmann, but on balance I suspect it was unintentional self-parody. EEng 03:04, 14 August 2023 (UTC)

Apart of sniggering, do you have something to say to the point? - Altenmann >talk 03:12, 14 August 2023 (UTC)

My comment just above is to the point -- for those with the wit to see it. EEng 05:38, 14 August 2023 (UTC)

common situation where point location is really needed - wrong type of point location, i.e., not the one desscibed in the article. - Altenmann >talk 17:47, 13 August 2023 (UTC)

Then you need to restate the statement of the problem, with refs, too. "point location" is a collocation, which may have different meanings, such as here, and in math you have to define a term and adhere to the definition. - Altenmann >talk 17:43, 13 August 2023 (UTC)

In this particular case "the disadvantage" is the confusion with the model used to describe the real-life problem. Bern used the correct model: the like of the hidden surface removal. - Altenmann >talk 17:45, 13 August 2023 (UTC)

Point location is a well-defined technical term in computational geometry referring to finding which cell of a planar or spatial subdivision contains a given point. That is the sense in which it is used in the abstract of the reference I gave for the mouse-click problem. There are many specific variations on the point location problem depending on where the subdivision comes from; not all are general purpose. The history DAG approach to point location in a Delaunay triangulation is a standard example; it only allows point location in Delaunay triangulations, not in general, but it is still a point location data structure. The reference I gave for the mouse-click example is another: it only allows point locations in the planar subdivisions formed by overlaid rectangles, but it is still a point location data structure. As its author clearly intended by describing it as a point location data structure in the abstract.

The biggest mistake in your comment is the word "the" in "the correct model". In computational geometry, especially, it is often essential to be able to understand the same problem through multiple equivalent models (for instance, through projective duality). —David Eppstein (talk) 17:47, 13 August 2023 (UTC)

Sure thing, start picking on my English, too. - Altenmann >talk 17:54, 13 August 2023 (UTC)

It seems you don't hear me: I am saying that the mouse-click problem is not " finding which cell of a planar or spatial subdivision ". Bern's article correctly states the mouse-click problem as a problem of location among overlapping objects - far not the same as inside a subdivision. - Altenmann >talk 17:54, 13 August 2023 (UTC)

It seems you have still not correctly read the short wording in the abstract, "Algorithms for point location in the visible scene are also given." Here, the visible scene is a subdivision of a plane, the field of view, obtained by projecting the rectangles onto the plane and overlaying them in visibility order. —David Eppstein (talk) 18:39, 13 August 2023 (UTC)

Nope. The cited article body clarifies what "point location in the visible scene" means: to locate the window containing a given mouse-click, that is, which rectangle is the highest along a given line of sight, i.e., a visibility-type problem among overlapping rectangular GUI items. That it is a subdivision is your interpretation, not author's. - Altenmann >talk 18:42, 13 August 2023 (UTC)

If you are still stuck on the fact that a problem can have multiple equivalent formulations, and blind to the fact that they are equivalent, even when a published reference tells you that, then I can't help you understand any better. I have repeatedly stated this issue with the multiplicity of equivalent formulations above, and you are still going on about how one of those formulations is not point location even though another one of them is. This is reaching the level of WP:IDHT. I can only repeat what I said earlier: if you do not understand this material, you should not be editing the article. If you cannot bring anything more to the conversation, I do not see any point in continuing it. —David Eppstein (talk) 19:26, 13 August 2023 (UTC)

The crux of the disagreement is that while a real-life problem can have multiple mathematical models, the model discussed in the wikipedia aricle is not the one used in the journal article cited. Hence the reference cited does not support the claim: the real-life problem is mouse-click location and its model in the article cited is not point location in a subdivision. Please provide a reference that mouse-click location may be modeled as point location in a subdivision. - Altenmann >talk 19:37, 13 August 2023 (UTC)

P.S. And as I hinted earlier twice already: please avoid personal attacks. - Altenmann >talk 19:40, 13 August 2023 (UTC)

The problem in the paper is exactly point location in a specific kind of subdivision, the subdivision you get from overlaid rectangles. The article discusses point location in many kinds of subdivisions: monotone subdivisions, triangulations, etc. I have already provided a reference; you refuse to understand it. Please stop your tendentious and ignorance-exposing edits. —David Eppstein (talk) 22:01, 13 August 2023 (UTC)

No it is not. <Sigh> quoting the source once again: to locate the window containing a given mouse-click, that is, which rectangle is the highest along a given line of sight. Meaning no subdivision is involved and rectangles are treated as they are, not "subdivision you get from overlaid rectangles". Nobody cares about subdivision: the goal is to get a GUI item (which is a rectangle). Subdivison in this context is your ungrounded speculation and you are refusing to read the cited article in its face value. And the described solution does not involve subdivision either: it is in terms of the rectangles, not subdivisions. Rectangles are inserted into and retrieved from a certain data structure. - Altenmann >talk 01:37, 14 August 2023 (UTC)

You keep repeating the part of the paper that formulates the problem in a different way, and you keep passing over in silence the part of the paper (the abstract) that describes the same problem as an instance of point location. In my reading of the paper, it was obvious to the author that point location in the visible scene was equivalent to the more complicated ray shooting formula used to actually solve the problem in the body in the paper, so obvious that he could use one in the abstract as a shorhand for the other and expect the target audience of computational geometers to understand that they referred to the same thing. Please address this point rather than continuing to go on about how the other part of the paper is phrased differently. I know it's phrased differently. That's not the point. —David Eppstein (talk) 06:00, 14 August 2023 (UTC)

And you keep passing over in silence that our article has a quite particular definition of what point location problem is. - Altenmann >talk 06:43, 14 August 2023 (UTC)

The abstract says "point location in the visible scene". Yes it is an instance of "point location". Just an article about acupuncture defines the problem of "point location" as a problem of finding a correct point on a human body to insert a needle. The subject of this wikipedia article is "point location" as defined in a specific way, namely location in a spatial subdivision, not in a scene and not on human's body, nor the location of a cellphone by pings from three cell towers (yes, it is a "point location" problem, too, but this problem is to find coordinates of a point where the cellphone is, not the location of a husband in the house of a mistress; the latter would be indeed "point location" in the sense of this article.). And Bern's article does not "formulate the problem in a different way", it gives an exact definition of the problem vaguely described in the summary as "point location in the visible scene". Bern's article contains no other formulation. And this formulation is different from the one used in the wikipedia article. - Altenmann >talk 06:43, 14 August 2023 (UTC)

Regarding repeated insults of my knowledgeability with ref to User:Jnc/Astronomer vs Amateur: I am not asking a ref for "The moon is not made of blue cheese"; I am asking a ref for "the Moon is made of blue cheese". I am surprised that the colleague does not see the difference. And instead of providing the requested ref, they resort to insults and removal of attention tags from the article. - Altenmann >talk 02:43, 14 August 2023 (UTC)

That is a false characterization of what has happened. You asked for a ref. I gave you the ref you asked for. You asked for an explanation of how that reference is relevant. I gave you that too. You kept on not getting it even after that, and are still not getting it and escalating to drama boards. —David Eppstein (talk) 03:26, 14 August 2023 (UTC)

And I gave you an explanation that your argument is invalid. Frankly, I would'nt go to 3RR, but your insults did piss me off. - Altenmann >talk 03:37, 14 August 2023 (UTC)

Summary of disagreement

The wikipedia article gives a definition: "problem is, given a partition of the space into disjoint regions, to determine the region where a query point lies." It is followed by an example which may be described as the "mouse click problem". (find which GUI element is clicked by mouse).

There is a significant difference between the real-world problem ("mouse click problem", MCP) and the mathematical model ("point location in spatial subdivision", PLP) which indeed, may be used to solve the MCP (but in a very cumbersome way, I may say).

My point is that I see no ref stating that MCP may be solved with the help of PLP. The footnote added does not state MLP as a case of PLP, nor the suggested solution uses PLP as an underlying model. (The article summary does say "Algorithms for point location in the visible scene are also given", but this is a vague statement; the exact def is in the article's Section 8 and it does not involve any "partition of the space into disjoint regions".) - Altenmann >talk 03:37, 14 August 2023 (UTC)

P.S. I did suggest rewriting the lede to make the problem definition more generic and involve a general-purpose identification of an object by a point, and the example in question would be good, but in the dust and smoke it went unnoticed. An interesting real-life problem would be in gaming: the user clicks the mouse, and the gaming engine traces the ray along the line of sight to locate the object clicked. - Altenmann >talk 03:49, 14 August 2023 (UTC)

Ray tracing really is a different problem, unless you want to formulate it as a messy problem in a five-dimensional Euclidean space of 3d rays, subdivided into 5d cells within which all rays go to the same obstacle. That would require sourcing and even if sources could be found it would be very technical. Also, you are still missing the point. The mouse click problem can be formulated as a special case of the problem of point location in a planar subdivision. It is not the most general formulation of the problem (but neither are the versions restricting the problem to monotone subdivisions or triangulations) and it is not spatial. You can make a spatial problem by using another a dimension to represent the prioritization of rectangles, but then you have a formulation that is not in terms of point location. You can also formulate the mouse click problem as a range minimization problem where the elements are rectangles, the ranges are the subsets of rectangles that contain a specific mouse click point, and the minimized values represent the prioritization; again, this is an equivalent problem but a different formulation (that is also not point location). —David Eppstein (talk) 06:03, 14 August 2023 (UTC)

"You can also formulate the mouse click problem as..." - almost correct, with the exception that a more precise statement would be "You can also model the mouse click problem as...". Mouse-click problem is a "real world problem" and "range minimization" or smth. else is a mathematical model. To solve the mouse click problem modeling it as an instance of point location in a spatial subdivision is even worse than the brute-force method of simply checking the point against all GUI rectangles (marked with their "height" in the GUI stack): surely you are aware that an overlay of N rectangles may generate a subdivision of size O(N^2). - Altenmann >talk 07:03, 14 August 2023 (UTC)

Its value as an example in the lead of this article is unrelated to its value as an implementation technique. Formulating the problem in this way is not the same as solving it. But also, if you had a subdivision that was changing infrequently and many point locations to perform, O(n^2) could be an acceptable price to pay in preprocessing to make the queries fast. The bigger problem with the windowing example is that the number of windows is likely small enough and the real-time response time needed slow enough that simply sequentially searching the ordered list of windows for the first one to contain the click would work well enough. —David Eppstein (talk) 07:13, 14 August 2023 (UTC)

Eppstein, in mathematic "to formulate a problem in a different way" is to give it a different, but an equivalent formulation. I already mentioned, the way you use the term is imprecise; the correct term would be "to model the (real-world) problem". Otherwise we may discuss a "spherical horse in vacuum" as a real thing. - Altenmann >talk 21:32, 14 August 2023 (UTC)

I don't see anything worthy of response to in this, other than to point out that I find the form of address you are using to be rude and insulting. Please do not do that. —David Eppstein (talk) 00:14, 15 August 2023 (UTC)

Please provide the preferred form of addressing to you. - Altenmann >talk 00:22, 15 August 2023 (UTC)

My full user name is always acceptable, because it is my user name. If you wish to refer to me by name rather than user name, then in the context of my professional expertise, which this is, "Dr. Eppstein" or "Prof. Eppstein" are both acceptable. (Mr. Eppstein is fine in non-technical contexts, but only in those contexts.) If you are from a Germanic-speaking nation that does this and want to be super formal, I won't complain if you use "Prof. Dr. Eppstein", but I would be skeptical of anyone else using that. If you were on friendly terms with me, which after dragging me to the drama boards you are not, I would instead suggest "David". One Wikipedia editor, a friend from long ago, gets to use a nickname; he knows who he is. —David Eppstein (talk) 06:19, 15 August 2023 (UTC)

Requested move 14 August 2023

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review after discussing it on the closer's talk page. No further edits should be made to this discussion.

The result of the move request was: No consensus. EdJohnston (talk) 20:10, 6 September 2023 (UTC)

---

Point location → Point location problem – confusingly ambiguous title: even search in Wikipedia gives more hits for the meaning "position, coordinates, of a point", not to say about the acupuncture meaning :-) - Altenmann >talk 01:52, 14 August 2023 (UTC) — Relisting. ModernDayTrilobite (talk • contribs) 16:06, 21 August 2023 (UTC)— Relisting. —usernamekiran (talk) 21:04, 29 August 2023 (UTC)

Oppose. There is no other article from which this needs disambiguation, so the argument that this is needed as WP:NATDIS does not work. This article is not merely about the problem of point location (that is, the specification of what the input-output behavior of a point location method should be) but also about its solutions, applications, etc. So tacking on "problem" to the article title is not merely pointless noise; it makes the title more specific in a way that it should not be. Additionally, it fails WP:COMMONNAME: searching Google Scholar for intitle:"point location" finds only one out of the first ten that uses "point location problem", and overall only 64 out of 921. It is used, but not frequently. (Before someone brings up WP:WAX arguments, the same thing applies to many of our other computer science articles on "X problem": in many cases, the "problem" part of the title is redundant or worse and should be removed.) —David Eppstein (talk) 03:08, 14 August 2023 (UTC)

I didnt request disambiguation, merely for a tighter term. As for the word "problem" in the title, we have plenty of " problem" pages (only recently I happened to edit "einstein problem") and it is only natural to talk in them about their solutions, extensions, and what's not. I can agree that in many cases the word "problem" is redundant, but I didn't think this is the case here, hence the move proposal. - Altenmann >talk 03:40, 14 August 2023 (UTC)

If you didn't request disambiguation, what is your "confusingly ambiguous title" supposed to mean? As for "as for the word "problem" in the title", that is exactly the sort of WP:WAX argument that I was hoping to preempt. —David Eppstein (talk) 05:58, 14 August 2023 (UTC)

• Support. Current title is ambiguous and confusing as nom points out. Proposed title is concise, common, and far more recognisable. Andrewa (talk) 02:57, 21 August 2023 (UTC)

Note: WikiProject Computer science has been notified of this discussion. ModernDayTrilobite (talk • contribs) 16:06, 21 August 2023 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Disputed 'cn' tag

"can be formulated as an instance of point location, with a subdivision formed by the visible parts of each window,{cn|date=August 2023|reason=the given footnote does not state mouse click location as location in some subdivision}" - Assuming I'm completely dimwitted, please quote from Bern's article where it speaks of "subdivision formed by the visible parts of each window" . - Altenmann >talk 07:46, 14 August 2023 (UTC)

I've done so several times, but here you go again:

"A simple but important special case of the hidden surface removal problem is one in which the scene consists of n rectangles with sides parallel to the x- and y-axes, with viewpoint at z=∞ (that is, an orthographic projection). This special case has application to overlapping windows in computer displays. ... Algorithms for point location in the visible scene are also given."

Here "visible scene" is exactly the same thing as "subdivision formed by the visible parts of each window", spelled out in less detail. The details about how this connects to mouse-clicks in the windows are later in the paper, as part of a different non-point-location formulation of the same problem, in a section for which the sentence "Algorithms ... are also given" is a summary. —David Eppstein (talk) 17:13, 14 August 2023 (UTC)

I've done so several times, but here you go again: "visible scene the same as a subdivision" is your unreferenced interpretation. In computer graphics, a scene is a collection of objects rendered (eg here, from David J. Eck, Introduction to Computer Graphics) and a visible scene is the part of the scene that is visible. Here scene is a collection of GUI rectangles to be rendered. - Altenmann >talk 17:18, 14 August 2023 (UTC)

That interpretation makes no sense, because then the problem to be solved in that interpretation of "scene" would be ray shooting, not point location, because the word "visible" would not be relevant to the scene, and because the sentence in the abstract would not describe anything within the paper. By elimination, only the interpretation I give is possible. As for "unreferenced": we do not need to add references to our references, and then references to our references to our references, etc. —David Eppstein (talk) 17:32, 14 August 2023 (UTC)

Yes it makes sense because in the discussed special case all scene objects happen to be in parallel planes (considering the "height" parameter, which is an abstraction of the order of drawing, and "ray shooting" degenerates into "point piercing"; as the article says it: "which rectangle is the highest along a given line of sight". And "a given line of sight" is a ray, isn't it? And the solution inserts scene rectangles into a segment tree without resorting to any "subdivision by the visible parts". And the "point location" problem in question is stated by Bern as "to locate the window", not "to determine the region [of a space subdivision]". And the irony about referencing is misplaced; yes we need to provide references to all disputed statements from the Wikipedia article. - Altenmann >talk 21:26, 14 August 2023 (UTC)

These tortured interpretations do not reflect the contents of the reference. —David Eppstein (talk) 00:12, 15 August 2023 (UTC)

I didn't put them into the article, do I? Yes IMO they reflect the content of the reference. If you disagree, please indicate the errors, so that a consensus can be reached. - Altenmann >talk 00:25, 15 August 2023 (UTC)

No. I disagree. I have already disagreed. The error is your entire argumentation here. There is nothing to point out. There is no possibility of consensus with someone so wrongheaded as you are being here. —David Eppstein (talk) 06:17, 15 August 2023 (UTC)

Concluding, Dr. Eppstein failed to quote a passage from the article cited that speaks anything about a subdivision in problem definition or solution. - Altenmann >talk 15:09, 15 August 2023 (UTC)

On the contrary, I have quoted multiple times a passage that you insist on reading incorrectly. —David Eppstein (talk) 17:19, 15 August 2023 (UTC)

I don't have to read anything "correctly" or "incorrectly": all I want to read is the word "subdivision" or its synonym in a quote from the article cited. - Altenmann >talk 19:44, 15 August 2023 (UTC)

This insistence on exact wording rather than on intended meaning is wrongheaded. —David Eppstein (talk) 19:54, 15 August 2023 (UTC)

Only if the "intended meaning" is author's, and the only way to figure out the intended meaning by Wikipedia rules is to cite published sources. - Altenmann >talk 22:07, 15 August 2023 (UTC)

Or you could, you know, read the paper, and discard interpretations that do not cause what it says to make any sense. —David Eppstein (talk) 23:10, 15 August 2023 (UTC)