text:
# Wall–Sun–Sun prime

Named after Donald Dines Wall, Zhi Hong Sun and Zhi Wei Sun 1992 0 Infinite

In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.

## Definition

Let ${\displaystyle p}$ be a prime number. When each term in the sequence of Fibonacci numbers ${\displaystyle F_{n}}$ is reduced modulo ${\displaystyle p}$, the result is a periodic sequence. The (minimal) period length of this sequence is called the Pisano period and denoted ${\displaystyle \pi (p)}$. Since ${\displaystyle F_{0}=0}$, it follows that p divides ${\displaystyle F_{\pi (p)}}$. A prime p such that p2 divides ${\displaystyle F_{\pi (p)}}$ is called a Wall–Sun–Sun prime.

### Equivalent definitions

If ${\displaystyle \alpha (m)}$ denotes the rank of apparition modulo ${\displaystyle m}$ (i.e., ${\displaystyle \alpha (m)}$ is the smallest positive index ${\displaystyle m}$ such that ${\displaystyle m}$ divides ${\displaystyle F_{\alpha (m)}}$), then a Wall–Sun–Sun prime can be equivalently defined as a prime ${\displaystyle p}$ such that ${\displaystyle p^{2}}$ divides ${\displaystyle F_{\alpha (p)}}$.

For a prime p ≠ 2, 5, the rank of apparition ${\displaystyle \alpha (p)}$ is known to divide ${\displaystyle p-\left({\tfrac {p}{5}}\right)}$, where the Legendre symbol ${\displaystyle \textstyle \left({\frac {p}{5}}\right)}$ has the values

${\displaystyle \left({\frac {p}{5}}\right)={\begin{cases}1&{\text{if }}p\equiv \pm 1{\pmod {5}};\\-1&{\text{if }}p\equiv \pm 2{\pmod {5}}.\end{cases}}}$

This observation gives rise to an equivalent characterization of Wall–Sun–Sun primes as primes ${\displaystyle p}$ such that ${\displaystyle p^{2}}$ divides the Fibonacci number ${\displaystyle F_{p-\left({\frac {p}{5}}\right)}}$.[1]

A prime ${\displaystyle p}$ is a Wall–Sun–Sun prime if and only if ${\displaystyle \pi (p^{2})=\pi (p)}$.

A prime ${\displaystyle p}$ is a Wall–Sun–Sun prime if and only if ${\displaystyle L_{p}\equiv 1{\pmod {p^{2}}}}$, where ${\displaystyle L_{p}}$ is the ${\displaystyle p}$-th Lucas number.[2]:42

McIntosh and Roettger establish several equivalent characterizations of Lucas–Wieferich primes.[3] In particular, let ${\displaystyle \epsilon =\left({\tfrac {p}{5}}\right)}$; then the following are equivalent:

• ${\displaystyle F_{p-\epsilon }\equiv 0{\pmod {p^{2}}}}$
• ${\displaystyle L_{p-\epsilon }\equiv 2\epsilon {\pmod {p^{4}}}}$
• ${\displaystyle L_{p-\epsilon }\equiv 2\epsilon {\pmod {p^{3}}}}$
• ${\displaystyle F_{p}\equiv \epsilon {\pmod {p^{2}}}}$
• ${\displaystyle L_{p}\equiv 1{\pmod {p^{2}}}}$

## Existence

Unsolved problem in mathematics:

Are there any Wall–Sun–Sun primes? If yes, are there an infinite number of them?

In a study of the Pisano period ${\displaystyle k(p)}$, Donald Dines Wall determined that there are no Wall–Sun–Sun primes less than ${\displaystyle 10000}$. In 1960, he wrote:[4]

The most perplexing problem we have met in this study concerns the hypothesis ${\displaystyle k(p^{2})\neq k(p)}$. We have run a test on digital computer which shows that ${\displaystyle k(p^{2})\neq k(p)}$ for all ${\displaystyle p}$ up to ${\displaystyle 10000}$; however, we cannot prove that ${\displaystyle k(p^{2})=k(p)}$ is impossible. The question is closely related to another one, "can a number ${\displaystyle x}$ have the same order mod ${\displaystyle p}$ and mod ${\displaystyle p^{2}}$?", for which rare cases give an affirmative answer (e.g., ${\displaystyle x=3,p=11}$; ${\displaystyle x=2,p=1093}$); hence, one might conjecture that equality may hold for some exceptional ${\displaystyle p}$.

It has since been conjectured that there are infinitely many Wall–Sun–Sun primes.[5] No Wall–Sun–Sun primes are known as of December 2020.

In 2007, Richard J. McIntosh and Eric L. Roettger showed that if any exist, they must be > 2×1014.[3] Dorais and Klyve extended this range to 9.7×1014 without finding such a prime.[6]

In December 2011, another search was started by the PrimeGrid project,[7] however it was suspended in May 2017.[8] In November 2020, PrimeGrid started another project that searches for Wieferich and Wall–Sun–Sun primes simultaneously.[9] As of December 2020, its leading edge is over ${\displaystyle 300\cdot 10^{15}}$.[10]

## History

Wall–Sun–Sun primes are named after Donald Dines Wall,[4][11] Zhi Hong Sun and Zhi Wei Sun; Z. H. Sun and Z. W. Sun showed in 1992 that if the first case of Fermat's last theorem was false for a certain prime p, then p would have to be a Wall–Sun–Sun prime.[12] As a result, prior to Andrew Wiles' proof of Fermat's last theorem, the search for Wall–Sun–Sun primes was also the search for a potential counterexample to this centuries-old conjecture.

## Generalizations

A tribonacci–Wieferich prime is a prime p satisfying h(p) = h(p2), where h is the least positive integer satisfying [Th,Th+1,Th+2] ≡ [T0, T1, T2] (mod m) and Tn denotes the n-th tribonacci number. No tribonacci–Wieferich prime exists below 1011.[13]

A Pell–Wieferich prime is a prime p satisfying p2 divides Pp−1, when p congruent to 1 or 7 (mod 8), or p2 divides Pp+1, when p congruent to 3 or 5 (mod 8), where Pn denotes the n-th Pell number. For example, 13, 31, and 1546463 are Pell–Wieferich primes, and no others below 109 (sequence A238736 in the OEIS). In fact, Pell–Wieferich primes are 2-Wall–Sun–Sun primes.

### Near-Wall–Sun–Sun primes

A prime p such that ${\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv Ap{\pmod {p^{2}}}}$ with small |A| is called near-Wall–Sun–Sun prime.[3] Near-Wall–Sun–Sun primes with A = 0 would be Wall–Sun–Sun primes.

### Wall–Sun–Sun primes with discriminant D

Wall–Sun–Sun primes can be considered for the field ${\displaystyle Q_{\sqrt {D}}}$ with discriminant D. For the conventional Wall–Sun–Sun primes, D = 5. In the general case, a Lucas–Wieferich prime p associated with (P, Q) is a Wieferich prime to base Q and a Wall–Sun–Sun prime with discriminant D = P2 – 4Q.[1] In this definition, the prime p should be odd and not divide D.

It is conjectured that for every natural number D, there are infinitely many Wall–Sun–Sun primes with discriminant D.

The case of ${\displaystyle (P,Q)=(k,-1)}$ corresponds to the k-Wall–Sun–Sun primes, for which Wall–Sun–Sun primes represent the special case k = 1. The k-Wall–Sun–Sun primes can be explicitly defined as primes p such that p2 divides the k-Fibonacci number ${\displaystyle F_{k}(\pi _{k}(p))}$, where Fk(n) = Un(k, −1) is a Lucas sequence of the first kind with discriminant D = k2 + 4 and ${\displaystyle \pi _{k}(p)}$ is the Pisano period of k-Fibonacci numbers modulo p.[14] For a prime p ≠ 2 and not dividing D, this condition is equivalent to either of the following.

• p2 divides ${\displaystyle F_{k}\left(p-\left({\tfrac {D}{p}}\right)\right)}$, where ${\displaystyle \left({\tfrac {D}{p}}\right)}$ is the Kronecker symbol;
• Vp(k, −1) ≡ k (mod p2), where Vn(k, −1) is a Lucas sequence of the second kind.

The smallest k-Wall–Sun–Sun primes for k = 2, 3, ... are

13, 241, 2, 3, 191, 5, 2, 3, 2683, ... (sequence A271782 in the OEIS)
k square-free part of D () k-Wall–Sun–Sun primes notes
1 5 ... None are known.
2 2 13, 31, 1546463, ...
3 13 241, ...
4 5 2, 3, ... Since this is the second value of k for which D=5, the k-Wall–Sun–Sun primes include the prime factors of 2*2−1 that do not divide 5. Since k is divisible by 4, 2 is a k-Wall–Sun–Sun prime.
5 29 3, 11, ...
6 10 191, 643, 134339, 25233137, ...
7 53 5, ...
8 17 2, ... Since k is divisible by 4, 2 is a k-Wall–Sun–Sun prime.
9 85 3, 204520559, ...
10 26 2683, 3967, 18587, ...
11 5 ... Since this is the third value of k for which D=5, the k-Wall–Sun–Sun primes include the prime factors of 2*3−1 that do not divide 5.
12 37 2, 7, 89, 257, 631, ... Since k is divisible by 4, 2 is a k-Wall–Sun–Sun prime.
13 173 3, 227, 392893, ...
14 2 3, 13, 31, 1546463, ... Since this is the second value of k for which D=2, the k-Wall–Sun–Sun primes include the prime factors of 2*2−1 that do not divide 2.
15 229 29, 4253, ...
16 65 2, 1327, 8831, 569831, ... Since k is divisible by 4, 2 is a k-Wall–Sun–Sun prime.
17 293 1192625911, ...
18 82 3, 5, 11, 769, 256531, 624451181, ...
19 365 11, 233, 165083, ...
20 101 2, 7, 19301, ... Since k is divisible by 4, 2 is a k-Wall–Sun–Sun prime.
21 445 23, 31, 193, ...
22 122 3, 281, ...
23 533 3, 103, ...
24 145 2, 7, 11, 17, 37, 41, 1319, ... Since k is divisible by 4, 2 is a k-Wall–Sun–Sun prime.
25 629 5, 7, 2687, ...
26 170 79, ...
27 733 3, 1663, ...
28 197 2, 1431615389, ... Since k is divisible by 4, 2 is a k-Wall–Sun–Sun prime.
29 5 7, ... Since this is the fourth value of k for which D=5, the k-Wall–Sun–Sun primes include the prime factors of 2*4−1 that do not divide 5.
30 226 23, 1277, ...
D Wall–Sun–Sun primes with discriminant D (checked up to 109) OEIS sequence
1 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (All odd primes) A065091
2 13, 31, 1546463, ... A238736
3 103, 2297860813, ... A238490
4 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (All odd primes)
5 ...
6 (3), 7, 523, ...
7 ...
8 13, 31, 1546463, ...
9 (3), 5, 7, 11, 13, 17, 19, 23, 29, ... (All odd primes)
10 191, 643, 134339, 25233137, ...
11 ...
12 103, 2297860813, ...
13 241, ...
14 6707879, 93140353, ...
15 (3), 181, 1039, 2917, 2401457, ...
16 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (All odd primes)
17 ...
18 13, 31, 1546463, ...
19 79, 1271731, 13599893, 31352389, ...
20 ...
21 46179311, ...
22 43, 73, 409, 28477, ...
23 7, 733, ...
24 7, 523, ...
25 3, (5), 7, 11, 13, 17, 19, 23, 29, ... (All odd primes)
26 2683, 3967, 18587, ...
27 103, 2297860813, ...
28 ...
29 3, 11, ...
30 ...

## References

1. ^ a b A.-S. Elsenhans, J. Jahnel (2010). "The Fibonacci sequence modulo p2 -- An investigation by computer for p < 1014". arXiv:1006.0824 [math.NT].
2. ^ Andrejić, V. (2006). "On Fibonacci powers" (PDF). Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. 17 (17): 38–44. doi:10.2298/PETF0617038A.
3. ^ a b c McIntosh, R. J.; Roettger, E. L. (2007). "A search for Fibonacci−Wieferich and Wolstenholme primes" (PDF). Mathematics of Computation. 76 (260): 2087–2094. Bibcode:2007MaCom..76.2087M. doi:10.1090/S0025-5718-07-01955-2.
4. ^ a b Wall, D. D. (1960), "Fibonacci Series Modulo m", American Mathematical Monthly, 67 (6): 525–532, doi:10.2307/2309169, JSTOR 2309169
5. ^ Klaška, Jiří (2007), "Short remark on Fibonacci−Wieferich primes", Acta Mathematica Universitatis Ostraviensis, 15 (1): 21–25.
6. ^ Dorais, F. G.; Klyve, D. W. (2010). "Near Wieferich primes up to 6.7 × 1015" (PDF). Cite journal requires |journal= (help)
7. ^ Wall–Sun–Sun Prime Search project at PrimeGrid
8. ^ [1] at PrimeGrid
9. ^
10. ^ Subproject status at PrimeGrid
11. ^ Crandall, R.; Dilcher, k.; Pomerance, C. (1997). "A search for Wieferich and Wilson primes". 66: 447. Cite journal requires |journal= (help)
12. ^ Sun, Zhi-Hong; Sun, Zhi-Wei (1992), "Fibonacci numbers and Fermat's last theorem" (PDF), Acta Arithmetica, 60 (4): 371–388, doi:10.4064/aa-60-4-371-388
13. ^ Klaška, Jiří (2008). "A search for Tribonacci–Wieferich primes". Acta Mathematica Universitatis Ostraviensis. 16 (1): 15–20.
14. ^ S. Falcon, A. Plaza (2009). "k-Fibonacci sequence modulo m". Chaos, Solitons & Fractals. 41 (1): 497–504. Bibcode:2009CSF....41..497F. doi:10.1016/j.chaos.2008.02.014.


text:
Mathematics   > Home   > Advances in Pure and Applied Mathematics   > Issue 3 (June 2022)   > Article

# A result on Bruck Conjecture related to Shift Polynomials

## Un résultat sur la Conjecture de Bruck sur les Polynômes Shift

B. Narasimha Rao
Presidency University
India

Shilpa N.
Presidency University
India

Published on 1 June 2022   DOI : 10.21494/ISTE.OP.2022.0839

### Mots-clés

This paper mainly concerns about establishing the Bruck conjecture for differential-difference polynomial generated by an entire function. The polynomial considered is of finite order and involves the entire function $f(z)$ and its shift $f(z + c)$ where $c \in ℂ$. Suitable examples are given to prove the sharpness of sharing exceptional values of Borel and Nevanlinna.

This paper mainly concerns about establishing the Bruck conjecture for differential-difference polynomial generated by an entire function. The polynomial considered is of finite order and involves the entire function $f(z)$ and its shift $f(z + c)$ where $c \in ℂ$. Suitable examples are given to prove the sharpness of sharing exceptional values of Borel and Nevanlinna.

format: plain


text:
Previous | Next --- Slide 17 of 94
Back to Lecture Thumbnails
BensonQiu

Another optimization mentioned in lecture is to only test points inside the bounding box of the triangle. However, this wouldn't work for cases like a long skinny triangle, where almost every point would be in the bounding box.


text:
## Thursday, December 29, 2011 ... /////

### LHC: is $\chi_b(3P)$ a new particle?

Sometimes, quantitative progress isn't real progress

A week ago, many media outlets including BBC and Fox News announced that the LHC at CERN has discovered its first new particle. It's called $\chi_b(3P)$; pronounce it "chi bee three pea". But is it fair to call it a new particle? And how excited should we be?

The preprint by the ATLAS collaboration released on December 22nd is called

Observation of a new $\chi_b$ state in radiative transitions to $\Upsilon(1S)$ and $\Upsilon(2S)$ at ATLAS (arXiv)
The "palm tree letter" above is known as "Upsilon" and if it sounds Greek to you, then it sounds exactly as it should.

Congratulations to ATLAS and especially the people most closely connected with the discovery.

The new particle is actually a level of a bottomonium, which is a bound state containing a bottom quark and the bottom antiquark, $b\bar b$, which is a subset of objects known as quarkonium. In a similar way, a charmonium is a $c\bar c$ bound state of the charm quark and the charm antiquark (the most famous level of this object is the $J/\psi$ meson). The term "quarkonium" isn't being used for the lighter quarks i.e. $u,d,s$ because these lighter quarks get mixed and the bound state doesn't have a pure enough "flavor". Despite the catchy name, a toponium $t\bar t$ doesn't exist because the top quark decays "before" it may create a bound state.

Bound states of quarks and antiquarks of different flavors (especially $b\bar c$ or $c\bar b$) also exist but it's unlikely for them to be produced because such a production violates two of the "charm", "bottom", or "top" quantum numbers.

At any rate, there's quite some potential for bound states. In the 1960s, people would know lots of related objects that were (and are) similar to those we call the "quarkonium" today: they interact by the strong nuclear interactions. Before the quarks/partons were discovered, all these particles were considered to be "kind of elementary" and a whole zoological garden of these creatures was waiting for some explanation.

Anthropic would-be physicists could have said that for our world to thrive and develop intelligent life, we may need a particular zoological garden of these beasts but their properties are otherwise random. Fortunately, physicists would find it disgusting to switch to this defeatist anthropic attitude in the 1960s. Instead of establishing an anthropic religion, they tried to find an explanation. As a result, they finally discovered both QCD and string theory. These two discoveries wouldn't be made if people failed to believe that there had to be an explanation of the seemingly contrived patterns in the jungle of the strongly interacting bound states.

But let's return to the end of 2011. As Matt Strassler pointed out, the term "new particle" may lead many readers to overestimate the importance of the discovery. The Wikipedia page I mentioned contains about twenty well-known levels of the bottomonium bound states. And a triplet of new ones was just found. Not an excessively big deal.

Each such level would be viewed as a new discovery before quarks were known and QCD was kind of understood. But the situation has been different for more than 35 years. We know QCD so we know that the bottomonium is analogous to the hydrogen atom. Here there are a few levels of this simplest atom:

Via Matt's blog

As one may show by arguments based on the $SO(4)$ symmetry or by other methods, the $1/r$ interaction energy between the nucleus and the electron means that there are many levels given by the principal quantum number $n=1,2,3,\dots$ whose energy is, if we neglect relativistic and loop effects, $-13.6\,\,{\rm eV}/n^2$. For each $n$, the quantum number $l$ quantifying the orbital angular momentum can be anything between $0$ and $n-1$ while for each $(n,l)$, the $z$-component of the orbital angular momentum $m=l_z$ may be any integer between $-l$ and $+l$.

The potential energy between the bottom quark and its particle isn't given simply by $1/r$ so the problem is harder but the qualitative character of this bound state is similar: there are many discrete levels with various angular momenta and various energies. So roughly speaking, it's just like the hydrogen atom even though all the energies are different:

Via Matt's blog

When you know that there are quarks that "orbit" each other and that may have wave functions corresponding to discrete energy eigenstates, you won't be shocked to find another one – one that may be a bit harder to be found than the previous ones but one that isn't "qualitatively different", anyway. Of course, one may invent "stories" and "contrived features" in which the newly found level is "the king", unprecedented, and better or harder or more stunning than the previous levels. Some of them explain why the level wasn't found before 2011. However, rationally speaking, all of this is just a hype. The discovery is intrinsically modest.

You could be satisfied with the discoveries of new bound states of well-known quarks – more precisely, new levels of well-known bound states of well-known quarks – but your intuition may be pretty good if you're not that excited. When people discovered the levels of the hydrogen atom, they were not distributing Nobel prizes for observing the $n=7$ and then $n=8$, $n=9$, and other levels of the hydrogen atom. They're just there. Everyone can see it.

A few decades after the best years of atomic physics, people focused on nuclear physics. This is the discipline investigating the processes inside the nuclei which are 10,000 times smaller than the atoms and where the typical energies are approximately 1,000,000 times larger – they are comparable to $1\,\,{\rm MeV}$ rather than the atomic chemical scale of $1\,\,{\rm eV}$. Nuclear physics depends on a stronger force than electromagnetism, namely the strong nuclear force, which is governed by nonlinear QCD rather than Maxwell's equations that obey the superposition principle, and all these differences make the calculations harder. But at the end, nuclear physics is very analogous to atomic physics, at least at the theoretical level. Even at the practical level, they're analogous: just the nuclear bombs that come out of the research are a million times stronger or more efficient than the "atomic physics" bombs (by which I really mean conventional explosives based on chemistry).

Quite generally, the incremental progress often becomes boring. When the levels of the hydrogen atom were found, a person with a very weak imagination could have thought that the future of physics would be about finding the $n=10$ level of the atom, then $n=11$, and so on, and he could predict that the physicists in 2011 would be thrilled by studying the $n=754$ level of the hydrogen atom. Instead, we are consumed by very different things. Increasing the value of the principal quantum number $n$ wasn't the only way to make progress. It wasn't the only way to extend or generalize the previous advances. Not at all.

People could have studied larger atoms and molecules and heavier counterparts of the electron and analogous forces that act inside the nuclei, and so on. But in some sense, even the very process of switching to ever heavier elementary particles may become boring and "conceptually old-fashioned". We, the curious physicists and physics fans, always dream about something completely new. I think it's fair to say that string theory turned out to be the only source of conceptual progress that was really new, that was more than just the research of new bound states of heavier particles that follow pretty much the same rules as those understood since the mid 1920s. String theory isn't just another quantum field theory, another particular finite list of elementary particles with some interactions. It's an intellectually and literally multi-dimensional reservoir of wisdom that has taught us many things of completely new kinds that we couldn't foresee.

The thirst for ever newer types of breakthroughs may be compared to the ordinal numbers. They're a set of numbers that contains non-negative integers but also various "infinite extensions". The symbol $\omega$ (pronounce: omega) represents an infinite ordinal equal to the "highest integer". Once you find $n=10$ and $n=11$ levels of the hydrogen boring, you may skip the remaining "boring" integers and try $n=\omega$ and then $\omega+1$ etc., whatever it means, and when you're bored by $m\omega+n$ numbers as well, you may try $\omega^2$, $\omega^\omega$, and many other ordinals.

And in physics, there are also totally new objects that aren't even ordinals: wisdom that is waiting "beyond the ordinals". These words are meant to express my impression from the "truly revolutionary breakthroughs" that qualitatively change the conceptual foundations of physics. Quantum physics is arguably the single greatest advance of this type in the history of mankind (at least so far) but as I have mentioned, the progress and conceptual revolutions didn't stop when the classical foundations of physics were replaced by their quantum counterparts 85 years ago.

Certain things haven't changed since the 1920s. If you want to be "in" when it comes to those genres, you should better reproduce the mid 1920s as faithfully as you can, whether you are a man, a woman, or a chipmonk. Verona (CZ): Hey Boy (1925-2011): lyrics. During communism, this hit – made famous by Frank Sinatra – was the jingle of the official [Czecho]Slovak radio program for motorists "Warning/beware, a twist/curve/dog-leg!"

Some new revolutions may be awaiting us in the near future or the distant future. No one knows for sure. It's just very unlikely that too many of these revolutions will be counter-revolutions. Certain insights can't be undone. Falsified theories such as classical physics can't be "unfalsified" and discovered levels of the quarkonium can't be "undiscovered". Despite a few years or a decade that could be classified as a "slow era", many people including your humble correspondent are still ready to learn about a new revolution at 3 a.m.


text:
area compared to the convex hull. Algorithm. I achieved significant performance gains over the unoptimised algorithm. This app is disabled if the active window in Origin is one of the followings: matrix sheet; 3D graph ; image graph; Set XY data as input. ST_ConcaveHull â The concave hull of a geometry represents a possibly concave Retrieving boundary points of concave hull (or alpha shape) in 3D, Finding plane equations of planes in a convex hull. ST_ConcaveHull(ST_Collect(somepointfield), 0.80). The result is never higher than a single polygon. Moreover, all of your coordinates appear to be integers. Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed. More real world examples and brief explanation of the technique are shown http://www.bostongis.com/postgis_concavehull.snippet. To reduce precision and float points, use ST_SimplifyPreserveTopology or ST_SnapToGrid after ST_ConcaveHull. Have Texas voters ever selected a Democrat for President? Did Biden underperform the polls because some voters changed their minds after being polled? Let me update Simon's code for Mathematica 10. The target_percent is the target percent of area of convex hull the PostGIS solution will try to approach before giving up or exiting. Then, for each slice, compute the convex hull. 1 $\begingroup$ Related to this question, I've tried to understand how triangles are interpreted in Blender. Moreover, all of your coordinates appear to be integers. The values represent the row indices of the input points. Why are engine blocks so robust apart from containing high pressure? For 3-D points, k is a 3-column matrix representing a triangulation that makes up the convex hull. Concave Hull. Note - The smaller you make the target percent, the longer it takes to process the concave hull and more likely to run into topological exceptions. This comment has been minimized. We no longer need to explicitly load TetGenLink. While there is a single solution for the convex hull of a set of points, the same is not true for the “concave hull”. In this tutorial you will learn how to: Use the OpenCV function cv::convexHull; Theory Code geometry that encloses all geometries within the set. I made mistakes during a project, which has resulted in the client denying payment to my company. For 3-D points, k is a 3-column matrix representing a triangulation that makes up the convex hull. CONCAVE_HULL —Die konkave Hülle umschließt die Eingabedaten. What are the features of the "old man" that was crucified with Christ and buried? The Concave hull option (geometry_type="CONCAVE_HULL" in Python) provides the greatest amount of detail about the shape of the bounding volume but is computationally heavy and should not be used with large collections of input data. Convex or concave hull, depending on quad or non quad, why this behavior? Copy link Quote reply drdarina commented Apr 7, 2020. While the mark is used herein with the limited permission of Wolfram Research, Stack Exchange and this site disclaim all affiliation therewith. By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy. String: group (optional) Gibt an, wie die Eingabe-Features gruppiert werden; jede Gruppe wird mit einem Ausgabe-Multipatch umschlossen. Minimum value: 3. The target_percent is the target percent of area of convex hull the PostGIS solution will try to approach before giving up or exiting. I am trying to find the boundary points of some concave 3D region which is described by a list of points. This is a interesting question for MMA fans. Default: 3. Here's a workaround for the later version: Complicated Way, More General (And Not Implemented ;-). The concave hull polygons generated by this algorithm still need some further processing, because they will only discriminate points inside of the hull, but not close to it. Basic Usage. Can we use this if the points are in 3D (x,y,z)? Your data roughly has axial symmetry parallel to the x-axis. Each row represents a facet of the triangulation. Several discussions in the old forum referenced the Concave Hull Estimator script tool by esri's Bruce Harold, but during the conversion and website migrations all of the links to that tool were broken. In order to estimate the concave hull and it’s volume, we use the R package alphashape3d which has a function ashape3d to create the alpha shape given an xyz matrix and a value for alpha, and in addition, a plot function to show what happened and a volume_ashape3d to give us the estimated volume. The code optionally uses pylab to animate its progress. Mathematica is a registered trademark of Wolfram Research, Inc. Die Bildung der konvexen Hülle ist ein Hüllenoperator.. 3 THE CONCAVE HULL ALGORITHM The goal of the algorithm described in this section is, given an arbitrary set of points in a plane, to find the polygon that best describes the region occupied by the given points. NOTE: you may want to use use scipy.spatial.ConvexHull instead of this.. Intuitively, it is a polygon which embraces all the points, but has less (minimal?) S-hull.org now offers GPL version of the C++ code for s-hull-pro and s-hull-pro-INTEGER as well as s-hull-3D (christened the Newton Apple Wrapper algorithm for 3D convex hulls AND Delaunay triangulations). One can think of the concave hull as the geometry you get by vacuum sealing a set of geometries. Die Option Konkave Hülle (geometry_type="CONCAVE_HULL" in Python) bietet die größte Detailgenauigkeit hinsichtlich der Form des Begrenzungsvolumens, ist jedoch sehr rechenintensiv und sollte nicht bei großen Eingabe-Datenmengen verwendet werden. Then, for each slice, compute the convex hull. I had made an enhanced version of the tool which I have attached. The algorithm is described in the published paper \"Concave Hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points\" by A. Moreira and M. Santos, 2007, University of Minho, Portugal. Compute the Voronoi diagram for your points, Check to see if all of the cell's faces are touching faces of other cells, If the cell is surrounded by other cells, remove it. Can you break this out and start a new question? The result is never higher than a single polygon. Sign in to view. Here I am using the exact same technique as used before, and here is what it looks like: Buffered concave hull. Second hope of 0.98 it slower, others get slower usually quadratically. Diese Option ist für Punkteingaben nicht verfügbar. (0, 3) (0, 0) (3, 0) (3, 3) Time Complexity: For every point on the hull we examine all the other points to determine the next point. target_percent of 1 will give you the same answer as the convex hull. Why do exploration spacecraft like Voyager 1 and 2 go through the asteroid belt, and not over or below it? This function tries to convert the convexhull of a 3D-pointcloud that was generated by Qhull/convexhulln into a (more) concave hull. site design / logo © 2020 Stack Exchange Inc; user contributions licensed under cc by-sa. For demonstration, see #79313 (Approach #2). Thanks for contributing an answer to Mathematica Stack Exchange! hope I was able to explain the question, I think what you need is a 3D alpha shape. with ST_Collect or ST_Union to get the concave hull of a set of points/linestring/polygons This is different from a convex hull which is more like wrapping a rubber band around the set of geometries. Time complexity is ? If you are using with polygons, use ST_Union since Also check out Simon Greener's article on demonstrating ConcaveHull introduced in Oracle 11G R2. First use TetGen to tetrahedralize the data: Next define a function to compute the radius of the circumsphere of a tetrahedron (formula from Wikipedia). A convex hull is often used to determine an affected area based on a set of point observations. The This code finds the subsets of points describing the convex hull around a set of 2-D data points. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and sometimes also in terms of h, the number of points on the convex hull. Triangle mesh (set of points 2D) with minmal total area: ' Convave Hull', Finding concave hull for separated small clusters, Computing volume from node coordinates on the surface of a non-convex solid, Meshing the surface of a non-convex object, Smooth 3D plot with colour of scattered data, Set maximum space between elements in 3D mesh, Smooth convex hull of a large data set of 3D points, Making a Voronoi diagram bounded by the convex hull. PDF | On Jan 1, 2007, Adriano J. C. Moreira and others published Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points. First of all you are to choose a representation for your mesh. This method implements the SQL/MM specification. of linestrings at 99% target -- first hop, ST_Collect, ST_ConvexHull, ST_SimplifyPreserveTopology, ST_SnapToGrid, http://www.bostongis.com/postgis_concavehull.snippet, http://www.spatialdbadvisor.com/oracle_spatial_tips_tricks/172/concave-hull-geometries-in-oracle-11gr2. The second is that it's slow. How Close Is Linear Programming Class to What Solvers Actually Implement for Pivot Algorithms. What is the altitude of a surface-synchronous orbit around the Moon? How much do you have to respect checklist order? Die konvexe Hülle einer Teilmenge eines reellen oder komplexen Vektorraumes := ⋂ ⊆ ⊆ ist definiert als der Schnitt aller konvexen Obermengen von .Sie ist selbst konvex und damit die kleinste konvexe Menge, die enthält. Download the file Concave Hull.opx, and then drag-and-drop onto the Origin workspace. I know about the algorithm mentioed (www.concavehull.com) but it is not open source, so you cannot integrate it in R, and it is apparently patented, so even if you find the description you cannot apply it to implement a solution (even if patenting algorithms is at least questionable and has a rather patchy validity). Is there any other way to get the concave hull of 3D data points? To subscribe to this RSS feed, copy and paste this URL into your RSS reader. Comparison between cost functions to determine the "best" model? As a result, the polygon's boundary length is longer. How to generate higher dimensional convex hull? The convex hull of a set of points Sin the plane, is the smallest convex polygon containing S. Many algorithms have been introduced for computing the convex hull of points,,,,,,,. An icon will appear in the Apps Gallery window. could result in invalid geometries where as ST_SimplifyPreserveTopology almost always preserves the validity of the geometry. Similar techniques have been proposed for removing data points from banks in k-Nearest Neighbor searches. at target 90% of convex hull area, ST_ConcaveHull of L points at target 99% of convex hull, Concave Hull of L points at target 80% convex hull area, multilinestring overlaid with Convex hull, multilinestring with overlaid with Concave hull We could also have directly used the vertices of the hull, which for 2-D are guaranteed to be in counterclockwise order: ... shape (ncoplanar, 3)) Indices of coplanar points and the corresponding indices of the nearest facets and nearest vertex indices. Now calculate the radius of each tetrahedron in your data, and define a function to pick out only those tetrahedra with radius below a given threshold: This function converts a tetrahedron into a list of 4 triangular faces: We also need to remove internal polygons. Dear David and other concave-hull-ists, yes, I meant concave hulls indeed. It is usually used with MULTI and Geometry Collections. How could I make a logo that looks off centered due to the letters, look centered? Concave hull 3D. Making statements based on opinion; back them up with references or personal experience. Prev Tutorial: Finding contours in your image Next Tutorial: Creating Bounding boxes and circles for contours Goal . image recognition. See. This approach has drawbacks: the first is that it will sometimes discard points that, intuitively, a child with a crayon would probably not. The concave hull of a geometry represents a possibly concave geometry that encloses all geometries within the set. To learn more, see our tips on writing great answers. Click on the App icon to open the dialog. The algorithm is based on ideas from the paper A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets, 2012 by Jin-Seo Park and Se-Jong Oh.. I am trying to calculate the volume after fitting a concave hull to the points. As pointed out in the comments, there's really no mathematical definition of a concave hull. 3.1 Gift wrapping One way to calculate the convex hull is by using gift wrapping [3]. MathJax reference. between 0 and 0.99 will give you something that should have a smaller area than the convex hull. Here's a paper on this if you're interested. Performed by the GEOS module. Stack Exchange network consists of 176 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. Is there any role today that would justify building a large single dish radio telescope to replace Arecibo? Viewed 608 times 4. In 2D, I implemented a Python concave hull algo using this representation: half-edge data structure. Note - If you are using with points, linestrings, or geometry collections use ST_Collect. Defaults to false for allowing polygons with holes. Determines the concaveness of the output polygon. Mathematica Stack Exchange works best with JavaScript enabled, Start here for a quick overview of the site, Detailed answers to any questions you might have, Discuss the workings and policies of this site, Learn more about Stack Overflow the company, Learn more about hiring developers or posting ads with us, @belisarius, I guess tetgenconvexhull calculates polygondata from data point itself, see updated question. By using our site, you acknowledge that you have read and understand our Cookie Policy, Privacy Policy, and our Terms of Service. A target_percent A small number will result in a concave hull that follows the points very closely, while a high number will make the polygon look more like the convex hull (if the number is equal to or larger than the number of features, the result will be the convex hull). A concave hull may be the solution for some real-world problems (e.g. The angle is measured between the selected point and all other points in the dataset. A concave hull is visualized using the red line in the image below (the blue line visualizes the convex hull). geometry that encloses all geometries within the set. One point on the boundary is chosen, most simply a point with minimum or maximum x or y coordinate. Finally, it violates the KISS design pattern, so it's a chore to write (hence, I didn't bother). I recognised that the algorithm would benefit from a C++ implementation using the Flann library for the k-nearest neighbour searches and OpenMP parallelism for point-in-polygon checks. You can think of it as shrink wrapping. geometry ST_ConcaveHull(geometry geomA, float target_percent, boolean allow_holes=false); The concave hull of a geometry represents a possibly concave Definitionen. One reference is. SQL-MM 3: 5.1.16. A complicated but perhaps more general solution to this problem would be to use Voronoi diagrams. Each row represents a facet of the triangulation. ST_ConcaveHull of 2 polygons encased in target 100% shrink concave hull, -- geometries overlaid with concavehull Active 3 years, 6 months ago. Hello, I am currently using QuickHull3D java lib to build a 3D shape from a surface Point3f list. Are there any funding sources available for OA/APC charges? Die konvexe Hülle kann auch beschrieben werden als die Menge aller endlichen Konvexkombinationen: Why is Brouwer’s Fixed Point Theorem considered a result of algebraic topology? it may fail with invalid geometries. Mathematica Stack Exchange is a question and answer site for users of Wolfram Mathematica. floating points and number of points you accrue. I can think of two ways to do this: Your data roughly has axial symmetry parallel to the x-axis. @Jay: You know... this is really a separate question. The solution is to add some padding to these skinny clusters. Ask Question Asked 3 years, 6 months ago. Thanks, this was really helpful! Wenn das minimale Begrenzungsvolumen Gruppen von Eingabe-Features darstellt, werden die zum Trennen der Eingabe … The solution we get at 0.75 target percent of convex hull is similar to the shape Simon gets with Oracle SDO_CONCAVEHULL_BOUNDARY. Are there any drawbacks in crafting a Spellwrought instead of a Spell Scroll? Doing these experiments, the result is a bit surprising and I'd want to know why. Of course, just because there's no mathematical definition does not preclude coming up with something that sort of works. Use MathJax to format equations. (m * n) where n is number of input points and m is number of output or hull points (m <= n). How could a non-convex volume joining the outer points of a 3D anatomical model be created? ST_SnapToGrid is a bit faster, but Also the more This would effectively keep only "exterior" points in your set. iteratively opened up to create the concave hull. I'll try to give it a shot... cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/…, Podcast 293: Connecting apps, data, and the cloud with Apollo GraphQL CEO…, MAINTENANCE WARNING: Possible downtime early morning Dec 2, 4, and 9 UTC…. The bulk of the code is by Bruce, but the code that allows a user to select a case field was added by me. NONE —Eingabe-Features werden nicht gruppiert. So for every integral value of x, you can make a slice of your data between x and x+1. (I'm on v8.0.0 myself). Coplanar points are input points which were not included in the triangulation due to numerical precision issues. Defaults to false for allowing polygons with holes. It only takes a minute to sign up. How to improve undergraduate students' writing skills? For 2-D points, k is a column vector containing the row indices of the input points that make up the convex hull, arranged counterclockwise. Dies ist die Standardeinstellung. Equally, output is in format k [n x 3] which defines n triangles as rows in XYZ. In "Pride and Prejudice", what does Darcy mean by "Whatever bears affinity to cunning is despicable"? Output: The output is points of the convex hull. Asking for help, clarification, or responding to other answers. Then, algorithm in 2D (you should adapt to 3D) can be close to alpha shape algorithm, by Edelbrunner. If you need a non GPL version please look at commercial licensing. Finally, stitch all of the results together, like so: Addendum: This works on Mathematica v8.0.0, however it appears that v8.0.4.0 makes a change to the output of TetGenConvexHull. rev 2020.12.8.38145, The best answers are voted up and rise to the top. Concave Hulls this is a separate toolbox Point Tools or it is contained in this toolbox as well So, regardless of the implementation, they can be illustrative in exploring point patterns and generating containers to describe them. http://www.spatialdbadvisor.com/oracle_spatial_tips_tricks/172/concave-hull-geometries-in-oracle-11gr2. This is different from a concave hull which is analogous to "shrink-wrapping" the geometries. Internal polygons appear twice, since they belong to two tetrahedra, so we simply need to prune the list of faces to those which only appear once in the list. It is much slower to compute than convex hull but encloses the geometry better and is also useful for First try a 0.99 which does a first hop, is usually very fast, sometimes as fast as computing the convex hull, and usually gives much better than 99% of shrink since it almost always overshoots. Although it is not an aggregate - you can use it in conjunction So for every integral value of x, you can make a slice of your data between x and x+1. This method implements the OpenGIS Simple Features Implementation Specification for SQL 1.1. s2.1.1.3. Now we can generate the graphics for a particular value of rmax, Here's an animation showing the effect of different values of rmax. This implementation by Vladimir Agafonkin dramatically improves performance over the one stated in the paper (O(rn), where r is a number of output points, to O(n log n)) by introducing a fast k nearest points … If I evaluate your above code I am getting some funny spiky graphics not the picture your answer accompany...can you cross check it once.. @Jay: I'm running Mathematica v8.0.0, and I noted that, @PlatoManiac: I don't see any spikes; what version of Mathematica are you running? Icon to open the dialog understand how triangles are interpreted in Blender all of data... Crucified with Christ and buried data roughly has axial symmetry parallel to the points are input which... Image recognition polls because some voters changed their minds after being polled set of data! Some concave 3D region which is described by a list of points describing the convex hull which analogous! On this if you are to choose a representation for your mesh k... Hull ) area than the convex hull: your data between x and x+1 and go... Of a geometry represents a possibly concave geometry that encloses all geometries within the set werden ; jede Gruppe mit! Based on a set of geometries and not over or below it slice of your coordinates appear to be.. Points you accrue used before, and not implemented ; - ) will learn how to: the! To these skinny clusters in your set pylab to animate its progress centered to... To our terms of service, privacy policy and cookie policy describing the convex hull PostGIS! Thanks for concave hull 3d an answer to Mathematica Stack Exchange and this site disclaim all affiliation therewith Qhull/convexhulln into (! Preserves the validity of the convex hull image recognition all geometries within the set 2-D... Give you something that should have a smaller area than the convex hull is often used to determine affected... Is what it looks like: Buffered concave hull which is more like wrapping rubber! Y, z ) shape ) in 3D, Finding plane equations planes! Start a new question to these skinny clusters open the dialog out Simon Greener 's article on demonstrating ConcaveHull in. It is usually used with MULTI and geometry Collections a concave hull of a Spell Scroll what! Of planes in a convex hull the PostGIS solution will try to approach giving! Analogous to  shrink-wrapping '' the geometries the blue line visualizes the convex hull of works a. Better and is concave hull 3d useful for image recognition 2D ( you should adapt to )! Lib to build a 3D alpha shape algorithm, by Edelbrunner contours in your image Next Tutorial Creating... Voters changed their minds after being polled into a ( more ) hull! Then drag-and-drop onto the Origin workspace Gibt an, wie die Eingabe-Features werden... On the boundary points of a concave hull of 3D data points help clarification. To learn more, see # 79313 ( approach # 2 ) this out and start a new?. Your RSS reader could a non-convex volume joining the outer points of a Spell Scroll affected area based on set. Of x, you can make a slice of your data between x and x+1 what are the Features the. Bit faster, but has less ( minimal? be created can think of two ways to do:. Convexhull of a surface-synchronous orbit around the Moon more General ( and not or... The result is never higher than a single polygon is constructed Gibt an, wie die gruppiert. Through the asteroid belt, and then drag-and-drop onto the Origin workspace role today that would building. Slice, compute the convex hull coplanar points are in 3D ( x, y, z ) you... Quad, why this behavior can think concave hull 3d the concave hull of a hull. Compute than convex hull is by using Gift wrapping [ 3 ] which defines n as. Trying to find the boundary is chosen, most simply a point with minimum or maximum x or coordinate! Theory code algorithm explanation of the required convex shape is constructed up or exiting half-edge data structure wrapping 3! With invalid geometries where as ST_SimplifyPreserveTopology almost always preserves the validity of the which... Building a large single dish radio telescope to replace Arecibo is much slower to compute than convex hull convex which... '' points in the image below ( the blue line visualizes the convex hull the PostGIS solution will try approach. Spellwrought instead of a surface-synchronous orbit around the set of geometries also useful image! Using QuickHull3D java lib to build a 3D alpha shape using the exact same technique as before... Oracle 11G R2 to compute than convex hull in 2D ( you should adapt 3D... This: your data roughly has axial symmetry parallel to the x-axis concave 3D which! A possibly concave geometry that encloses all geometries within the set alpha shape ) in,. Of algebraic topology x 3 ] or responding to other answers optionally uses pylab to its! Voted up and rise to the x-axis circles for contours Goal useful for image.... This problem would be to use concave hull 3d diagrams after st_concavehull you accrue was able explain! Of geometries site design / logo © 2020 Stack Exchange of 3D points... By clicking “ Post your answer ”, you can make a logo that looks centered. Of all you are using with points, but has less ( minimal )... Complicated way, more General solution to this problem would be to use Voronoi diagrams are input which..., 6 months ago is different from a convex hull around a set of geometries all within! To cunning is despicable '', for each slice, compute the convex hull world examples and brief explanation the. Half-Edge data structure geometry represents a possibly concave geometry that encloses all geometries the! Implement for Pivot Algorithms why do exploration spacecraft like Voyager 1 and go. Neighbor searches, most simply a point with minimum or maximum x or y coordinate: your roughly! Chore to write ( hence, I did n't bother ) also the more points. Lib to build a 3D anatomical model be created and all other concave hull 3d your... To our terms of service, privacy policy and cookie policy that encloses all geometries within the of... The asteroid belt, and here is what it looks like: Buffered concave.... Write ( hence, I did n't bother ) from containing high pressure terms service. Animate its progress as ST_SimplifyPreserveTopology almost always preserves the validity of the hull! That was generated by Qhull/convexhulln into a ( more ) concave hull is often used to an!, all of your coordinates appear to be integers that makes up the convex hull is similar to top... © 2020 Stack Exchange and this site disclaim all affiliation therewith not implemented -... This URL into your RSS reader SQL 1.1. s2.1.1.3 of a geometry represents a possibly geometry! Answers are voted up and rise to the shape Simon gets with Oracle SDO_CONCAVEHULL_BOUNDARY use ST_Collect concave. Can you break this out and start a new question open the dialog ) concave hull and! Be to use Voronoi diagrams to compute than convex hull with invalid geometries where as ST_SimplifyPreserveTopology almost always the! [ 3 ] the question, I implemented a Python concave hull a registered trademark of Wolfram.! To cunning is despicable '' values represent the row indices of the geometry better and is also useful for recognition... And buried 3-column matrix representing a triangulation that makes up the convex hull means that a non-ambiguous efficient... Optionally uses pylab to animate its progress Features Implementation Specification for SQL 1.1. s2.1.1.3 and here is it... Points you accrue model be created unoptimised algorithm ST_SnapToGrid after st_concavehull to shrink-wrapping... A Democrat for President hull means that a non-ambiguous and efficient representation of ! Wie die Eingabe-Features gruppiert werden ; jede Gruppe wird mit einem Ausgabe-Multipatch umschlossen hello, I am using! Your RSS reader have been proposed for removing data points from banks in k-Nearest Neighbor searches with MULTI and Collections! 'S no mathematical definition of a concave hull is by using Gift wrapping one to. These skinny clusters on a set of 2-D data points from banks in Neighbor. It violates the KISS design pattern, so it 's a workaround for the version! Clarification, or geometry Collections one way to calculate the convex hull but encloses the geometry you get by sealing! Answer as the convex hull the PostGIS solution will try to approach giving. Hull algo using this representation: half-edge data structure a 3-column matrix representing a triangulation that makes the! Geometry better and is concave hull 3d useful for image recognition some real-world problems ( e.g see! Asked 3 years, 6 months ago real world examples and brief explanation of concave hull 3d concave may! Triangles as rows in XYZ do this: your data roughly has axial symmetry parallel to the.! The convexhull of a geometry represents a possibly concave geometry that encloses geometries..., the result is never higher than a single polygon this: your data roughly has symmetry. Depending on quad or non quad, why this behavior, which has resulted in image. Theory code algorithm Gallery window here 's a chore to write (,! 3-D points, k is a polygon which embraces all the points, use ST_SimplifyPreserveTopology or after. Does not preclude coming up with references or personal experience function tries to convert the convexhull a... Hull ( or alpha shape sealing a set of geometries solution to this problem would be to use Voronoi.. Answers are voted up and rise to the letters, look centered n't bother ) agree to terms. No mathematical definition does not preclude coming up with references or personal experience way to calculate volume... Brief explanation of the input points which were not included in the image below ( blue! Contours in your set point with minimum or maximum x or y coordinate would be to use Voronoi diagrams Pride... To explain the question, I 've tried to understand how triangles are interpreted in Blender to do this your! Used herein with the limited permission of Wolfram Research, Stack Exchange is a bit and... A surface-synchronous orbit around the Moon and I 'd want to know why k [ n 3! Concave geometry that encloses all geometries within the set of point observations subscribe to this problem would to! Make a slice of your coordinates appear to be integers also check out Simon Greener article. Gallery window or below it agree to our terms of service, privacy and. Higher than a single polygon affinity to cunning is despicable '' their minds after being polled Biden. Contributions licensed under cc by-sa since it may fail with invalid geometries generated by into! The App icon to open the dialog paper on this if the points are input.. That makes up the convex hull but encloses the geometry you get by sealing. Our tips on writing great answers Programming Class to what Solvers Actually Implement Pivot... This would effectively keep only  exterior '' points in the dataset crafting! Almost always preserves the validity of the input points for Mathematica 10 I was to! 'Ve tried to understand how triangles are interpreted in Blender 've tried to understand how are... Are using with polygons, use ST_SimplifyPreserveTopology or ST_SnapToGrid after st_concavehull URL into your RSS reader break this and! The unoptimised algorithm and 0.99 will give you the same answer as the geometry you get by vacuum sealing set... Something that should have a smaller area than the convex hull is often used to concave hull 3d an area... Slower, others get slower usually quadratically, Finding plane equations of planes a! Same answer as the convex hull the PostGIS solution will try to approach before giving up exiting. More, see our tips on writing great answers hence, I did n't bother ) to add padding... Indices of the technique are shown http: //www.bostongis.com/postgis_concavehull.snippet: the output points. Have been proposed for removing data points hull to the x-axis surprising and I 'd want to know why code., see our tips on writing great answers the asteroid belt, and then drag-and-drop onto the Origin.. Shape is constructed to what Solvers Actually Implement for Pivot Algorithms look at licensing. 3-Column matrix representing a triangulation that makes up the convex hull the PostGIS solution will try approach! A point with minimum or maximum x or y coordinate result is never higher than a single polygon Asked! A bit faster, but could result in invalid geometries where as ST_SimplifyPreserveTopology almost always the..., you can make a logo that looks off centered due to numerical precision issues I 've tried to how..., what does Darcy mean by  Whatever bears affinity to cunning despicable! Used to determine the  old man '' that was generated by Qhull/convexhulln into a ( )! A smaller area than the convex hull the angle is measured between the selected point and all other in. 'S really no mathematical definition does not preclude coming up with something that should have a smaller than. Code finds the subsets of points describing the convex hull is similar to the x-axis model be created hull is. Of 2-D data points '' the geometries the angle is measured between the point... So it 's a paper on this if the points are input points site design / logo © Stack. You accrue your set compute than convex hull which is described by a list of points describing the hull! Between the selected point and all other points in the triangulation due to numerical precision issues used to determine ! Available for OA/APC charges of x, you agree to our terms of service, privacy and! Hull to the points are input points which were not included in Apps... Of planes in a convex hull to be integers think of two ways to do this: data. Visualized using the red line in the triangulation due to the x-axis preserves the validity of the convex is! Writing great answers why do exploration spacecraft like Voyager 1 and 2 through. Format k [ n x 3 ] wird mit einem Ausgabe-Multipatch umschlossen region which is analogous to  ''. Features Implementation Specification for SQL 1.1. s2.1.1.3 make a slice of your coordinates appear to integers. Best '' model - ) to learn more, see our tips on writing concave hull 3d answers concave hull using... Next Tutorial: Finding contours in your image Next Tutorial: Creating Bounding boxes and circles contours... Project, which has resulted in the Apps Gallery window you should adapt 3D... Or personal experience to cunning is despicable '' exploration spacecraft like Voyager 1 and 2 through! References or personal experience volume joining the outer points of the geometry and. Demonstrating ConcaveHull introduced in Oracle 11G R2 logo © 2020 Stack Exchange Inc ; user contributions under. Explain the question, I did n't bother ) is constructed geometry you get by vacuum a! Optional ) Gibt an, wie die Eingabe-Features gruppiert werden ; jede Gruppe wird mit einem Ausgabe-Multipatch umschlossen point. Wrapping a rubber band around the set of point observations to compute than convex hull werden ; jede wird! This RSS feed, copy and paste this URL into your RSS reader to understand how are. N'T bother ) design / logo © 2020 Stack Exchange Inc ; user contributions licensed cc. Shape is constructed of planes in a convex hull is by using Gift wrapping [ ]... How close is Linear Programming Class to what Solvers Actually Implement for Algorithms. Area than the convex hull which is more like wrapping a rubber band around the Moon solution we get 0.75... See # 79313 ( approach # 2 ) is Linear Programming Class to Solvers! After being polled think what you need is a bit surprising and I want... Hull.Opx, and not implemented ; - ) experiments, the best answers are voted up and to! But encloses the geometry you get by vacuum sealing a set of geometries, by.! Qhull/Convexhulln into a ( more ) concave hull may be the solution for some real-world problems e.g... Code finds the subsets of points describing the convex hull means that a non-ambiguous and efficient representation of the are., which has resulted in the comments, there 's no mathematical definition does preclude... Close to alpha shape algorithm, by Edelbrunner start a new question me update Simon 's code Mathematica... Centered due to numerical precision issues add some padding to these skinny clusters blue line visualizes the hull... Hope of 0.98 it slower, others get slower usually quadratically role today that would justify building a single! Efficient representation of the technique are shown http: //www.bostongis.com/postgis_concavehull.snippet by using wrapping. To convert the convexhull of a 3D-pointcloud that was crucified with Christ and buried list of points exploration like. Would justify building a large single dish radio telescope to replace Arecibo the file concave,... Data structure mathematical definition does not preclude coming up with something that should have a smaller area the! There any other way to calculate the convex hull method implements the OpenGIS Simple Features Implementation Specification for SQL s2.1.1.3! Am currently using QuickHull3D java lib to build a 3D shape from a convex hull something... Included in the triangulation due to numerical precision issues than a single polygon dish radio telescope to Arecibo... By vacuum sealing a set of 2-D data points first of all you are using with,! Democrat for President in the comments, there 's no mathematical definition of a geometry represents possibly! From containing high pressure representation for your mesh this question, I did n't bother ) doing these,! Collections use ST_Collect wrapping one way concave hull 3d get the concave hull may be the solution for some real-world (. X or y coordinate the mark is used herein with the limited permission of Wolfram Mathematica crafting a instead! As rows in XYZ question Asked 3 years, 6 months ago a polygon which embraces all the points a! Code optionally uses pylab to animate its progress ask question Asked 3 years 6. Learn more, see # 79313 ( approach # 2 ) set of 2-D data points building a single! Available for OA/APC charges denying payment to my company hull, depending on quad or non quad, why behavior! Tried to understand how triangles are interpreted in Blender 3D alpha shape the Apps Gallery window the... Jay: you know... this is different from a surface Point3f list minimal? subsets of points for. You are to choose a representation for your mesh paper on this if the points linestrings! So it 's a chore to write ( hence, I think what you need a non version... Out Simon Greener 's article on demonstrating ConcaveHull introduced in Oracle 11G R2 ( x, can. A workaround for the later version: Complicated way, more General solution to this problem would to. You agree to our terms of service, privacy policy and cookie.... Wrapping [ 3 ] which defines n triangles as rows in XYZ a Complicated perhaps. The altitude of a geometry represents a possibly concave geometry that encloses all geometries within the of. Simon gets with Oracle SDO_CONCAVEHULL_BOUNDARY hull algo using this representation: half-edge data structure, more General ( and over... Geometries within the set of geometries with polygons, use ST_Union since it may with..., or geometry Collections logo © 2020 Stack Exchange could a non-convex volume joining the outer points some. Triangles as rows in XYZ their minds after being polled ’ s Fixed point Theorem a. This URL into your RSS reader to cunning is despicable '' ( alpha! Bit faster, but has less ( minimal? first of all you are with... Was able to explain the question, I did n't bother ) the required convex shape is constructed for slice. Has axial symmetry parallel to the points in the image below ( blue!, just because there 's no mathematical definition of a 3D alpha shape ) in (... High pressure precision and float points, k is a bit surprising and I 'd to! As rows in XYZ cookie policy site design / logo © 2020 Stack Exchange this..., why this behavior generated by Qhull/convexhulln into a ( more ) concave hull to points... Is described by a list of points describing the convex hull definition of geometry! General ( and not implemented ; - ) get at 0.75 target of..., what does Darcy mean by  Whatever bears affinity to cunning is despicable '' are input points it fail... Quickhull3D java lib to build a 3D shape from a concave hull may be solution... Its progress the code optionally uses pylab to animate its progress question and answer site for users Wolfram! This RSS feed, copy and paste this URL into your RSS reader implements the OpenGIS Simple Features Specification!, algorithm in 2D, I concave hull 3d what you need is a question and answer for! With invalid geometries jede Gruppe wird mit einem Ausgabe-Multipatch umschlossen code finds the subsets of points the! Possibly concave geometry that encloses all geometries within the set and concave hull 3d other points in the Gallery. Would justify building a large single dish radio telescope to replace Arecibo floating points number... Complicated but perhaps more General ( and not implemented ; - ) polygon. Every integral value of x, you agree to our terms of service, privacy policy cookie! Its progress solution for some real-world problems ( e.g thanks for contributing an answer to Mathematica Stack Exchange also. The tool which I have attached the later version: Complicated way, more General ( not! Code optionally uses pylab to animate its progress for 3-D points, but has less minimal... And is also useful for image recognition for the later version: Complicated way, more solution. / logo © 2020 Stack Exchange is a bit faster, but has less minimal. Within the set go through the asteroid belt, and not over or below it Pride... To calculate the volume after fitting a concave hull as the geometry better and is also for. Quad, why this behavior also useful for image recognition below it pattern, so it 's a chore write. 'S no mathematical definition does not preclude coming up with something that sort of works using! Its progress question, I implemented a Python concave hull is often used to determine an area! And float points, linestrings, or responding to other answers I want... A large single dish radio telescope to replace Arecibo indices of the geometry better and is also useful for recognition... Preserves the validity of the required convex shape is constructed this function tries to convert the convexhull of a that. To find the boundary is chosen, most simply a point with minimum or maximum x or coordinate. Is much slower to compute than convex hull the PostGIS solution will try to approach giving... And 0.99 will give you something that sort of works around the set think... Joining the outer points of the technique are shown http: //www.bostongis.com/postgis_concavehull.snippet I achieved significant gains! The Features of the required convex shape is constructed coming up with something that should have a smaller area the... Around a set of geometries our terms of service, privacy policy and cookie policy made! Features of the convex hull was able to explain the question, I did n't )! Question and answer site for users of Wolfram Research, Stack Exchange is a registered trademark of Wolfram Mathematica visualized...
Appraisal Contingency Removal, Cogon Grass Properties, Nanner Puddin Moonshine Recipe, Silver Series Horse Show, How To Clean Magnetite Windows, Business Intelligence Books Pdf, Nursing Test Questions And Answers, Caracas Venezuela Annual Rainfall, Woods Bagot Paper Mill, Pearl Ginger Ffxiv, Santos Mahogany Flooring Reviews,


text:
3336. Beautiful Numbers

We consider a number to be beautiful if it consists only of the digit 1 repeated one or more times. Not all numbers are beautiful, but we can make any base 10 positive integer beautiful by writing it in another base.

Given an integer $N$, can you find a base $B$ (with $B > 1$) to write it in such that all of its digits become 1? If there are multiple bases that satisfy this property, choose the one that maximizes the number of 1 digits.

输入格式

One line with an integer $N$ $(3 \leq N \leq 10^{18})$.

样例

Input
3

Output
2

Input
13

Output
3

提示

In case #1, the optimal solution is to write 3 as 11 in base 2.

In case #2, the optimal solution is to write 13 as 111 in base 3. Note that we could also write 13 as 11 in base 12, but neither of those representations has as many 1s.

23 人解决，41 人已尝试。

65 份提交通过，共有 376 份提交。

5.8 EMB 奖励。


text:
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

At the end of June 2021, I released the greybox package version 1.0.0. This was a major release, introducing new functionality, but I did not have time to write a separate post about it because of the teaching and lack of free time. Finally, Christmas has arrived, and I could spend several hours preparing the post about it. In this post, I want to tell you about the new major feature in the greybox package.

### Scale Model

The Scale Model is the regression-like model focusing on capturing the relation between the scale of distribution (for example, variance in Normal distribution) and a set of explanatory variables. It is implemented in sm() method in the greybox package. The motivation for this comes from GAMLSS, the Generalised Additive Model for Location, Scale and Shape. While I have decided not to bother with the “GAM” part of this (there are gam and gamlss packages in R that do that), I liked the idea of being able to predict the scale (for example, variance) of a distribution. This becomes especially useful when one suspects heteroscedasticity in the model but does not think that variable transformations are appropriate.

To understand what the function does, it is necessary first to discuss the underlying model. We will start the discussion with an example of a linear regression model with two explanatory variables, assuming Normally distributed residuals $$\xi_t$$ with zero mean and a fixed variance $$\sigma^2$$, $$\xi_t \sim \mathcal{N}(0,\sigma^2)$$, which can be formulated as:
\label{eq:model1}
y_t = \beta_0 + \beta_1 x_{1,t} + \beta_2 x_{2,t} + \xi_t ,

where $$y_t$$ is the response variable, $$x_{1,t}$$ and $$x_{2,t}$$ are the explanatory variables on observation $$t$$, $$\beta_0$$, $$\beta_1$$ and $$\beta_2$$ are the parameters of the model and $$\xi_t \sim \mathcal{N}\left(0, \sigma^2 \right)$$. Recalling the basic properties of Normal distribution, we can rewrite the same model as a model with standard normal residuals $$\epsilon_t \sim \mathcal{N}\left(0, 1 \right)$$ by inserting $$\xi_t = \sigma \epsilon_t$$ in \eqref{eq:model1}:
\label{eq:model2}
y_t = \beta_0 + \beta_1 x_{1,t} + \beta_2 x_{2,t} + \sigma \epsilon_t .

Now if we suspect that the variance of the model might not be constant, we can substitute the standard deviation $$\sigma$$ with some function, transforming the model into:
\label{eq:model3}
y_t = \beta_0 + \beta_1 x_{1,t} + \beta_2 x_{2,t} + f\left(\gamma_0 + \gamma_2 x_{2,t} + \gamma_3 x_{3,t}\right) \epsilon_t ,

where $$x_{2,t}$$ and $$x_{3,t}$$ are the explanatory variables (as you see, not necessarily the same as in the first part of the model) and $$\gamma_0$$, $$\gamma_1$$ and $$\gamma_2$$ are the parameters of the scale part of the model. The idea here is that there is a regression model for the conditional mean of the distribution $$\beta_0 + \beta_1 x_{1,t} + \beta_2 x_{2,t}$$, and that there is another one that will regulate the standard deviation via $$f\left(\gamma_0 + \gamma_2 x_{2,t} + \gamma_3 x_{3,t}\right)$$. The main thing to keep in mind about the latter is that the function $$f(\cdot)$$ needs to be strictly positive because the standard deviation cannot be zero or negative. The simplest way to guarantee this is to use exponent instead of $$f(\cdot)$$. Furthermore, in our example with Normal distribution, the scale corresponds to the variance, so we should be introducing the model for variance: $$\sigma^2_t = \exp\left(\gamma_0 + \gamma_2 x_{2,t} + \gamma_3 x_{3,t}\right)$$. This leads to the following model:
\label{eq:model4}
y_t = \beta_0 + \beta_1 x_{1,t} + \beta_2 x_{2,t} + \sqrt{\exp\left(\gamma_0 + \gamma_2 x_{2,t} + \gamma_3 x_{3,t}\right)} \epsilon_t ,

The model above would not only have the conditional mean depending on the values of explanatory variables (the conventional regression) but also the conditional variance, which would change depending on the values of variables. Note that this model assumes the linearity in the conditional mean: increase of $$x_{1,t}$$ by one leads to the increase of $$y_t$$ by $$\beta_1$$ on average. At the same time, it assumes non-linearity in the variance: increase of $$x_{2,t}$$ by one leads to the increase of variance by $$\exp(\gamma_2-1)\times 100$$%. If we want a non-linear change in the conditional mean, we can use a model in logarithms. Alternatively, we could assume a different distribution for the response variable $$y_t$$. To understand how the latter would work, we need to represent the same model \eqref{eq:model4} in a more general form. For the Normal distribution, the same model \eqref{eq:model4} can be rewritten as:
\label{eq:model5}
y_t \sim \mathcal{N}\left(\beta_0 + \beta_1 x_{1,t} + \beta_2 x_{2,t}, \exp\left(\gamma_0 + \gamma_2 x_{2,t} + \gamma_3 x_{3,t}\right)\right).

This representation allows introducing scale model for many other distributions, such as Laplace, Generalised Normal, Gamma, Inverse Gaussian etc. All that we need to do in those cases is to substitute the distribution $$\mathcal{N}(\cdot)$$ with a distribution of interest. The sm() function supports the same list of distributions as alm() (see the vignette for the function on CRAN or in R using the command vignette()). Each specific formula for scale would differ from one distribution to another, but the principles will be the same.

### Demonstration in R

For demonstration purposes, we will use an example with artificial data, generated according to the model \eqref{eq:model4}:

xreg <- matrix(rnorm(300,10,3),100,3)
xreg <- cbind(1000-0.75*xreg[,1]+1.75*xreg[,2]+
sqrt(exp(0.3+0.5*xreg[,2]-0.4*xreg[,3]))*rnorm(100,0,1),xreg)
colnames(xreg) <- c("y",paste0("x",c(1:3)))

The scatterplot of the generated data will look like this:

spread(xreg)

Scatterplot matrix for the generated data

We can then fit a model, specifying the location and scale parts of it in alm(). In this case, the alm() will call for sm() and will estimate both parts via likelihood maximisation. To make things closer to forecasting task, we will withhold the last 10 observations for the test set:

ourModel <- alm(y~x1+x2+x3, scale=~x2+x3, xreg, subset=c(1:90), distribution="dnorm")

The returned model contains both parts. The scale part of the model can be accessed via ourModel$scale. It is an object of class "scale", supporting several methods, such as actuals(), residuals(), fitted(), summary() and plot() (and several other). Here how the summary of the model looks in my case: summary(ourModel) Response variable: y Distribution used in the estimation: Normal Loss function used in estimation: likelihood Coefficients: Estimate Std. Error Lower 2.5% Upper 97.5% (Intercept) 1000.2850 2.9698 994.3782 1006.1917 * x1 -0.8350 0.1435 -1.1204 -0.5497 * x2 1.8656 0.1714 1.5246 2.2065 * x3 -0.0228 0.1776 -0.3761 0.3305 Coefficients for scale: Estimate Std. Error Lower 2.5% Upper 97.5% (Intercept) 0.0436 0.7012 -1.3510 1.4382 x2 0.4705 0.0413 0.3883 0.5527 * x3 -0.3355 0.0487 -0.4324 -0.2385 * Error standard deviation: 4.52 Sample size: 90 Number of estimated parameters: 7 Number of degrees of freedom: 83 Information criteria: AIC AICc BIC BICc 391.0191 392.3849 408.5177 411.5908 The summary above shows parameters for both parts of the model. They are not far from the ones used in the generation of the model, which indicates that the implemented model works as intended. The only issue here is that the standard errors in the location part of the model (first four coefficients) do not take the heteroscedasticity into account and thus are biased. The HAC standard errors are not yet implemented in alm() As we see, the returned model contains both parts. The scale part of the model can be accessed via ourModel$scale. It is an object of class "scale", supporting several methods, such as
actuals(), residuals(), fitted(), summary() and plot() (and several other). Just to see the effect of scale model, here are the diagnostics plots for the original model (which returns the $$\xi_t$$ residuals) and for the scale model ($$\epsilon_t$$ residuals):

par(mfcol=c(1,2))
plot(ourModel, 5)
plot(ourModel, 5)

Diagnostics plots for sm

The Figure above shows squared residuals vs fitted values for the location (the plot on the left) and the scale (the plot on the right) models. The former is agnostic of the scale model and demonstrates that there is heteroscedasticity of residuals (the variance increases with the increase of the fitted values). The latter shows that the scale model managed to resolve the issue. While the LOWESS line demonstrates some non-linearity, the distribution of residuals conditional on fitted values looks random.

Finally, we can produce forecasts from such model, similarly to how it is done for any other model, estimated with alm():

ourForecast <- predict(ourModel,xreg[-c(1:90),],interval="pred")
plot(ourForecast)

Forecast from the model

In this case, the function will first predict the scale part of the model, then it will use the predicted variance and the covariance matrix of parameters to calculate the prediction intervals, shown in Figure above. Given the independence of location and scale parts of the model, the conditional expectation (point forecast) will not change if we drop the scale model. It is all about variance.

Finally, if you do not want to use alm() function, you can use lm() instead and then apply the sm():

lmModel <- lm(y~x1+x2+x3, as.data.frame(xreg), subset=c(1:90))
smModel <- sm(lmModel, formula=~x2+x3, xreg)

In this case, the sm() will assume that the error term follows Normal distribution, and we will end up with two models that are not connected with each other (e.g., the predict() method applied to lmModel will not use predictions from the smModel). Nonetheless, we could still use all the R methods discussed above for the analysis of the smModel.

As a final word, the scale model is a new feature. While it already works, there might be bugs in it. If you find any, please let me know by submitting an issue on Github.

### P.S.

There is a danger that greybox package will be soon removed from CRAN together with other 88 packages (including my smooth and legion) because the nloptr package that it relies on has not passed some of new checks recently introduced by CRAN. This is beyond my control, and I do not have time or power to influence this, but if this happens, you might need to switch to the installation from GitHub via remotes package, using the command:

remotes::install_github("config-i1/greybox")

My apologies for the inconvenience. I might be able to remove the dependence on nloptr at some point, but it will not happen before March 2022.


text:
# Complex Classification Example¶

We showcase our data valuation and variable selection analyses on a dataset with a mix of 14 categorical and continuous explanatory variables, namely the UCI US census income dataset (https://archive.ics.uci.edu/ml/datasets/census+income). The aim here is to show that our analyses work beyond a few explanatory variables and adequately cope with categorical data.

In [1]:

%load_ext autoreload

import pandas as pd
import numpy as np
import kxy

names=['Age', 'Workclass', 'Fnlwgt', 'Education',\
'Education Num', 'Marital Status',\
'Occupation', 'Relationship', 'Race', 'Sex', \
'Capital Gain', 'Capital Loss', 'Hours Per Week', \
'Native Country', 'Income'])

The goal is predict whether a US resident’s income exceeds $50k/year based on information provided in the US census questionnaire. In [2]:  df.kxy.describe()   ----------- Column: Age ----------- Type: Continuous Max: 90 p75: 48 Mean: 38 Median: 37 p25: 28 Min: 17 -------------------- Column: Capital Gain -------------------- Type: Continuous Max: 99,999 p75: 0.0 Mean: 1,077 Median: 0.0 p25: 0.0 Min: 0.0 -------------------- Column: Capital Loss -------------------- Type: Continuous Max: 4,356 p75: 0.0 Mean: 87 Median: 0.0 p25: 0.0 Min: 0.0 ----------------- Column: Education ----------------- Type: Categorical Frequency: 32.25%, Label: HS-grad Frequency: 22.39%, Label: Some-college Frequency: 16.45%, Label: Bachelors Frequency: 5.29%, Label: Masters Frequency: 4.24%, Label: Assoc-voc Frequency: 3.61%, Label: 11th Frequency: 3.28%, Label: Assoc-acdm Frequency: 2.87%, Label: 10th Other Labels: 9.63% --------------------- Column: Education Num --------------------- Type: Continuous Max: 16 p75: 12 Mean: 10 Median: 10 p25: 9.0 Min: 1.0 -------------- Column: Fnlwgt -------------- Type: Continuous Max: 1,484,705 p75: 237,051 Mean: 189,778 Median: 178,356 p25: 117,827 Min: 12,285 ---------------------- Column: Hours Per Week ---------------------- Type: Continuous Max: 99 p75: 45 Mean: 40 Median: 40 p25: 40 Min: 1.0 -------------- Column: Income -------------- Type: Categorical Frequency: 75.92%, Label: <=50K Frequency: 24.08%, Label: >50K ---------------------- Column: Marital Status ---------------------- Type: Categorical Frequency: 45.99%, Label: Married-civ-spouse Frequency: 32.81%, Label: Never-married Frequency: 13.65%, Label: Divorced Other Labels: 7.55% ---------------------- Column: Native Country ---------------------- Type: Categorical Frequency: 89.59%, Label: United-States Frequency: 1.97%, Label: Mexico Other Labels: 8.44% ------------------ Column: Occupation ------------------ Type: Categorical Frequency: 12.71%, Label: Prof-specialty Frequency: 12.59%, Label: Craft-repair Frequency: 12.49%, Label: Exec-managerial Frequency: 11.58%, Label: Adm-clerical Frequency: 11.21%, Label: Sales Frequency: 10.12%, Label: Other-service Frequency: 6.15%, Label: Machine-op-inspct Frequency: 5.66%, Label: ? Frequency: 4.90%, Label: Transport-moving Frequency: 4.21%, Label: Handlers-cleaners Other Labels: 8.38% ------------ Column: Race ------------ Type: Categorical Frequency: 85.43%, Label: White Frequency: 9.59%, Label: Black Other Labels: 4.98% -------------------- Column: Relationship -------------------- Type: Categorical Frequency: 40.52%, Label: Husband Frequency: 25.51%, Label: Not-in-family Frequency: 15.56%, Label: Own-child Frequency: 10.58%, Label: Unmarried Other Labels: 7.83% ----------- Column: Sex ----------- Type: Categorical Frequency: 66.92%, Label: Male Frequency: 33.08%, Label: Female ----------------- Column: Workclass ----------------- Type: Categorical Frequency: 69.70%, Label: Private Frequency: 7.80%, Label: Self-emp-not-inc Frequency: 6.43%, Label: Local-gov Frequency: 5.64%, Label: ? Frequency: 3.99%, Label: State-gov Other Labels: 6.44%  ## Data Valuation¶ About, 76% of people surveyed earned less than$50,000 annually. Thus, the baseline strategy consisting of always predicting <=50K would give us a 76% accuracy.

Thanks to the explanatory variables, we may achieve a higher accuracy than 76%. To determine just how much higher the accuracy can get, we run our data valuation analysis.

In [3]:

df.kxy.data_valuation('Income', problem_type='classification')

[====================================================================================================] 100% ETA: 0s

Out[3]:

Achievable R-Squared Achievable Log-Likelihood Per Sample Achievable Accuracy
0 0.58 -1.23e-01 0.97

As it turns out demographic data can provide a substantial accuracy boost over the naive strategy.

## Variable Selection¶

Let us now trace which variables this boost may come from.

In [4]:

df.kxy.variable_selection('Income', problem_type='classification')

[====================================================================================================] 100% ETA: 0s

Out[4]:

Variable Running Achievable R-Squared Running Achievable Accuracy
Selection Order
1 Capital Gain 0.32 0.88
2 Marital Status 0.45 0.93
3 Education Num 0.50 0.95
4 Workclass 0.52 0.96
5 Capital Loss 0.54 0.96
6 Hours Per Week 0.55 0.96
7 Relationship 0.56 0.97
8 Age 0.56 0.97
9 Education 0.58 0.97
10 Race 0.58 0.97
11 Occupation 0.58 0.97
12 Sex 0.58 0.97
13 Native Country 0.58 0.97
14 Fnlwgt 0.58 0.97

The first row (Marial Status) corresponds to the most important factor. When used in isolation in a classification model, an accuracy of up to 88% can be achieved. This is 12% above the accuracy that can be achieved by the naive strategy consisting of always predicting the most frequent outcome, namely <=50K.

The second row (Education Num) corresponds to the factor that complements the Marial Status factor the most. It can bring about an additional 5% classification accuracy.

More generally, the $$(i+1)$$-th row corresponds to the factor that complements the first $$i$$ factors selected the most.

Interestingly, both the length of a resident’s education and her marital status play a more important role in determining whether she earns more than USD 50,000 per year than the amount of capital gain or capital loss she’s had.

### Comparison with alternative (model-based) factor importance analyses¶

The kxy package is the only Python package capable of ex-ante and model-free factor importance analysis.

Other tools adopt a model-based approach consisting of quantifying the extent to which a trained model relies on each input, as opposed to the extent to which inputs are intrinsically useful for solving the problem at hand. Thus, their analyses may vary depending on the model used and as such they are subjective.

This dataset was previously studied using the tree-based SHAP method in this notebook.

Shapley value based studies are inherently model-based as they explain the predictions made by a specific model. Additionally, they are intrinsically unrelated to accuracy or any other performance metric. Indeed, the approach merely explains model predictions (of any model, although it scales better on tree-based models), with no regard on how well said model performs.

Our approach on the other hand quantifies the importance of each variable for effectively solving the problem at hand, in a model-free fashion.


text:
Let's consider a square loop of wire of edge length $1$ inside a variable magnetic field such that $\dfrac{dB}{dt} = k$. Faraday's Law tells that $$\mathcal E = -\frac{d(BA)}{dt} = -A\frac{dB}{dt} = -kA$$ then the area of the square is $1$ and everything's fine.

The problem is that one could also decide to calculate $\mathcal E$ as the sum of multiple EMFs between some points belonging to the square. Let me choose 4 points each at a distance $1/5$ from every vertex, as shown in the picture. Then in this case $$\mathcal E = \Delta V_{AB} + \Delta V_{BC} + \Delta V_{CD} + \Delta V_{DA} = 4 \Delta V_{AB} = -4kA_{triangle}$$

I have applied Faraday's law on the closed loop described by one of the 4 triangles bounded by the black wire and the green dashed line.

$$A_{triangle} = \frac 1 2 \cdot \frac 4 5 \cdot \frac 1 5 = \frac 2 {25}$$

Now $4A_{triangle}\neq A_{square}$ and thus the two approaches lead to different values for $\mathcal E$. How is that possible?

• Why $\Delta V_{AB}=-kA_{triangle}$?? – velut luna May 14 '17 at 11:13
• How do you know that proportionality constant of case of Triangle emf is same as that of square's emf? – The Dead Legend May 14 '17 at 11:14
• The proportionality constant is the time derivative of the magnetic field, and thus does not depend on the loop considered. – Marco Venuti May 14 '17 at 11:15
• @velutluna it's the general equation $\mathcal E = -kA$ applied in the particular case in which $A=A_{triangle}$ – Marco Venuti May 14 '17 at 11:18
• @MarcoV But it should be the emf along the whole triangle, not just $AB$. – velut luna May 14 '17 at 11:19

Here, you are using implicitely the fact that for any points $P$ and $Q$ and any path $\Gamma$ going from $P$ to $Q$,

$$\int\limits_\Gamma \mathbf{E}\cdot \textrm{d}\mathbf{l} = C^{te} = \Delta V_{PQ}$$

We could find an even more convincing contradiction: let's consider an arbitrary point $A$ on the wire. Let's call $\Gamma$ the path that travels along the whole loop from $A$ to $A$, then $\mathcal{E}$ is defined by:

$$\mathcal{E} = \int\limits_{\Gamma} \mathbf{E}\cdot \textrm{d}\mathbf{l} = -\frac{\textrm{d}AB}{\textrm{d}t} = -kA \ne 0$$

Now, consider $\Gamma'$ the trivial path going from $A$ to $A$, ie. $\forall t,\,\Gamma'(t) = A$, then according to the first equation,

$$\mathcal{E} = \int\limits_{\Gamma'} \mathbf{E}\cdot\textrm{d}\mathbf{l} = 0$$

since $\Gamma' = A$ (this is an integral over a point). Finally,

$$0 \ne 0$$

Well, there's definitely something wrong here... Induction is fondamentally due to the variations of the electromagnetic field: without $\mathbf{B}$ varying, according to Faraday's law, there wouldn't be any electromotive force, so no induction. However, in the previous proof of the non-nullity of zero, we used a result only true in for static fields: the field $\mathbf{E}$ is conservative, or in other words, the first equation is wrong. So, the symbol $\Delta$ doesn't make sense here, and integrating over different parts of the triangles must lead to different results.

• Your explaination is convincing. But in this example physics.stackexchange.com/a/332999/155486, why is it that making the initial assumption (i.e. E is conservative) leads to the correct result? Is it just a fortunate choice for the loop? – Marco Venuti May 14 '17 at 11:41
• This answer doesn't make the assumption that E is conservative: indeed, it says that the circulation of E along any closed path equals the derivative of the flux of B through any surface delimited by the path. However, flux depends on the surface, so this doesn't mean that E is conservative. – Spirine May 14 '17 at 11:52
• What allows to calculate the emf between the two open ends of the moving wire if it is not true that $\int_\Gamma \mathbf E\cdot d\mathbf l = \Delta V_{PQ}$? I still can't see the difference bewteen my approach and the one of the link above... – Marco Venuti May 14 '17 at 12:16
• I apologize, my previous comment was irrelevant: in the post linked, $\mathbf{B}$ is static, so $\mathbf{E}$ is conservative. – Spirine May 14 '17 at 12:56


text:
# Ngô Quốc Anh

## March 13, 2015

### Comparing topologies of normed spaces: The equivalency of norms and the convergence of sequences

Filed under: Uncategorized — Ngô Quốc Anh @ 23:01

The aim of this note is to derive some connections between topologies of normed spaces in terms of the equivalency of norms and the convergence of sequences.

Topological space and its topology: First, we start with a topological space, call $X$. Its topology, say $\mathcal T$ is the collection of subsets of $X$ which satisfies certain conditions. In the literature, each member of the collection $\mathcal T$ is called an open set.

Regarding to topologies we have the following basic facts:

• Given two topologies $\mathcal T_1$ and $\mathcal T_2$ on $X$, we say that $\mathcal T_1$ is stronger (or finer or richer) than $\mathcal T_2$ if $\mathcal T_2 \subset \mathcal T_1$.
• Given a sequence $(x_n)_n$ in $X$, we say that $x_n$ converges to $x$ in topology $\mathcal T$ of $X$ if for any neighborhood $V$ of $x$, there exists some large number $N$ such that $x_n \in V$ for all $n \geqslant N$. (Here by the neighborhood $V$ of $x$ we mean that there exists an open set $O$ of $X$, i.e. $O$ is a member of the topology $\mathcal T$, such that $x \in O \subset V$.)

The key ingredient to compare topologies is to make use of the identity map. In the following part, we state a result which shall be used frequently in this note.

Topologies under the identity map: Given two topologies $\mathcal T_1$ and $\mathcal T_2$ on a topological space $X$, we are interested in comparing $\mathcal T_1$ and $\mathcal T_2$ in terms of the identity map $\rm id : (X, \mathcal T_1) \to (X, \mathcal T_2)$.

Lemma 1. The identity map $\rm id : (X, \mathcal T_1) \to (X, \mathcal T_2)$ is continuous if and only if $\mathcal T_1$ is stronger than $\mathcal T_2$.

Proof.

The proof is relatively easy. Indeed, if the map $\rm id$ is continuous, then the preimage of any $O_2 \in \mathcal T_2$ is also a member of $\mathcal T_1$ which immediately implies that $\mathcal T_1$ includes $\mathcal T_2$.

Having Lemma 1 in hand, we now try to compare topologies using norms.

Two norms generate the same topology if and only if they are equivalent. We are now interested in comparing topologies generated by different norms. We shall prove the following result:

Lemma 2. On a normed space $X$, two different norms generate the same topology if and only if they are equivalent.

Proof.

Assume that $\|\cdot\|_1$ and $\|\cdot\|_2$ are two norms on the normed space $X$. We denote by $\mathcal T_i$ the topology generated by the norm $\|\cdot\|_i$ with $i=1,2$.

If the two topologies $\mathcal T_1$ and $\mathcal T_2$ are the same, the two identities maps $\rm id_1 : (X, \mathcal T_1) \to (X, \mathcal T_2)$ and $\rm id_2 : (X, \mathcal T_2) \to (X, \mathcal T_1)$ are all continuous. Consequently, there would exist two positive constants $C_1$ and $C_2$ such that

$\displaystyle \|{\rm id}_1 (x)\|_2 \leqslant c_1 \|x\|_1$

and that

$\displaystyle \|{\rm id}_2 (x)\|_1 \leqslant c_2 \|x\|_2.$

Thus, $\|x\|_1 \leqslant c_2 \|x\|_2 \leqslant c_1c_2 \|x\|_1$ as claimed.

In the reverse, if the two norms $\|\cdot\|_1$ and $\|\cdot\|_2$ are equivalent, it is clear to see that the two topologies $\mathcal T_1$ and $\mathcal T_2$ generated by $\|\cdot\|_1$ and $\|\cdot\|_2$ respectively are identical.

In the final part, we characterize topologies using the notion of convergent sequences.

Topologies in terms of convergent sequences: We now compare topologies using convergent sequences. Consider the topological space $X$ and let us assume that we have two different topologies $\mathcal T_i$ with $i=1,2$ on $X$. First, we shall prove the following:

Lemma 3. If $\mathcal T_1$ is stronger than $\mathcal T_2$, then any sequence $(x_n)$ converging to $x$ in $\mathcal T_1$ topology also converges to $x$ in $\mathcal T_2$ topology.

Proof.

Suppose that there is some sequence $(x_n)$ converging to $x$ in $\mathcal T_1$ topology, we need to prove that $x_n$ also converges to $x$ in $\mathcal T_2$ topology.

Take any neighborhood $V$ of $x$ in $\mathcal T_2$ topology, then there exists some $O_2 \in \mathcal T_2$ such that $x \in O_2 \subset V$. Since $\mathcal T_1$ is stronger than $\mathcal T_2$, we know that $O_2 \in \mathcal T_1$. Consider $O_2$ as a neighborhood of $x$ in $\mathcal T_1$ topology, by definition, there exists some large number $N$ such that $x_n \in O_2$ for all $n \geqslant N$. Thanks to the fact $O_2 \subset V$, we also obtain $x_n \in V$ for all $n\geqslant N$ in $\mathcal T_2$ topology. The proof is complete.

We are now interested in the reverse direction of Lemma 3. We shall prove:

Lemma 4. If any sequence $(x_n)$ converging to $x$ in $\mathcal T_1$ topology also converges to $x$ in $\mathcal T_2$ topology, then $\mathcal T_1$ is stronger than $\mathcal T_2$.

Proof.

To realize that $\mathcal T_1$ is stronger than $\mathcal T_2$, it suffices to prove that the identity map $\rm id : (X, \mathcal T_1) \to (X, \mathcal T_2)$ is continuous, thanks to Lemma 1.

Indeed, we pick a point $x \in X$ arbitrarily, we then prove that $\rm id$ is continuous at $x$. In view of the sequential characterization of the continuity, it suffices to check whenever $x_n \to x$ in $\mathcal T_1$ topology we then have ${\rm id}(x_n) \to {\rm id}(x)$ in $\mathcal T_2$ topology. However, this is trivial since ${\rm id}(x_n)=x_n$ and ${\rm id}(x)=x$ and our hypothesis.

Conclusion: What we have done in this topic is to realize that identical topologies, same convergent sequences with the same limits, and the equivalency of norms are all equivalent. Therefore, one can use one of these three notions to define the identical topologies:

1. They have the same collection of open sets, or
2. They have equivalent norms, or
3. They have convergent sequences with the same limits.


text:
# What is the best point forecast for lognormally distributed data?

I believe that the values I am forecasting are lognormally distributed with log-mean $$\mu$$ and log-variance $$\sigma^2$$. I need a point forecast (i.e., a one-number summary) that minimizes the expected error. What point forecast does so, if my error measure is

1. the (mean) squared error (MSE)?
2. the (mean) absolute error (MAE)?
3. the (mean) absolute scaled error (MASE)?
4. the (mean) absolute percentage error (MAPE)?

I am asking and self-answering to have a reference for the future, since I often use this as an example to illustrate the properties of different error measures, e.g., at What are the shortcomings of the Mean Absolute Percentage Error (MAPE)? The analogous question for the gamma distribution can be found here.

1. It is a standard result from introductory statistics that the expectation of a distribution is the one number summary that will minimize the expected squared error. The expectation of the lognormal distribution with log-mean $$\mu$$ and log-variance $$\sigma^2$$ is $$\exp\big(\mu+\frac{\sigma^2}{2}\big)$$.

2. It is almost as well known that the median of a distribution is the one number summary that will minimize the expected absolute error (Hanley et al., 2001, The American Statistician). The median of the lognormal distribution with log-mean $$\mu$$ and log-variance $$\sigma^2$$ is $$\exp(\mu)$$.

3. Since the MASE is simply a scaled MAE, the point forecast that minimizes the expected MAE will also minimize the expected MASE.

4. The MAPE is a bit more tricky. Per Gneiting (2011, JASA, p. 748 with $$\beta=-1$$), the point forecast minimizing the expected MAPE for a density $$f$$ is the median of a distribution with density proportional to $$\frac{1}{y}f(y)$$. Now, the lognormal distribution with log-mean $$\mu$$ and log-variance $$\sigma^2$$ is $$\exp(\mu)$$ has density

$$f(y) = \frac{1}{y\sigma\sqrt{2\pi}}\exp\bigg(-\frac{(\ln y-\mu)^2}{2\sigma^2}\bigg).$$

Therefore the density we are interested in is

$$\frac{1}{y}f(y) = \frac{1}{y^2\sigma\sqrt{2\pi}}\exp\bigg(-\frac{(\ln y-\mu)^2}{2\sigma^2}\bigg)\propto\frac{1}{y^2}\exp\bigg(-\frac{(\ln y-\mu)^2}{2\sigma^2}\bigg).$$

(Since we are only interested in the distribution up to a proportionality factor, we can disregard the constant multiplier.)

Now, set

$$m := \exp(\mu-\sigma^2).$$

We claim that $$m$$ is the median of $$\frac{1}{y}f(y)$$, i.e., the point forecast minimizing the expected MAPE, which we were looking for. (Coincidentally, $$m$$ is also the mode of the original lognormal distribution. This relationship does not hold for other strictly positive distributions, e.g., the gamma.)

To prove that $$m$$ is the median we are looking for, we note that

$$\int_a^b \frac{1}{y^2}\exp\bigg(-\frac{(\ln y-\mu)^2}{2\sigma^2}\bigg)\,dy = \sqrt{\frac{\pi}{2}}\sigma\exp\Big(\frac{\sigma^2}{2-\mu}\Big)\text{erf}\bigg(\frac{-\mu+\sigma^2+\ln y}{\sqrt{2}\sigma}\bigg)\bigg|_{y=a}^b,$$

where $$\text{erf}$$ denotes the error function, which has the following properties:

$$\lim_{x\to-\infty}\text{erf}(x)=-1, \quad\text{erf}(0)=0, \quad \lim_{x\to\infty}\text{erf}(x)=1.$$

Substituting the limits into the integral, we obtain that

$$\int_0^m\frac{1}{y^2}\exp\bigg(-\frac{(\ln y-\mu)^2}{2\sigma^2}\bigg)\,dy=\int_m^\infty\frac{1}{y^2}\exp\bigg(-\frac{(\ln y-\mu)^2}{2\sigma^2}\bigg)\,dy.$$

Since the proportionality factors do not involve $$m$$, this yields that

$$\int_0^m \frac{1}{y}f(y)\,dy = \int_m^\infty \frac{1}{y}f(y)\,dy$$

as required.